39. Combination Sum.md

39. Combination Sum (Medium)

[tag] BFS, Combination

• use DFS for combination problem
• sort list first

'''
since its a combination problem, DFS can be used.
void dfs(candidates, target, temp, ans, sum).
exit condition:
if sum > target or if index > len(candidates):
    return 
if sum == target:
    ans.append(temp)
    return
for i in range(index, len(candidates))
temp.append()
dfs()
temp.pop

2 3 6 7 
2   3   6   7
2 2 | 2 3| 2 6| 2 7|
'''
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        cur_sum = 0
        candidates.sort()
        def dfs(index, cur_sum):
            # print(cur_sum)
            if cur_sum > target or index > len(candidates):
                return 
            if cur_sum == target:
                # print(temp)
                ans.append(temp.copy())
                return
            for i in range(index, len(candidates)):
                temp.append(candidates[i])
                dfs(i, cur_sum + candidates[i])
                temp.pop()
        dfs(0, 0)
        return ans