Leetcode-Solutions/combination-sum.py at main · pskth/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ''' Not Efficient code, just tried a solution'''
        curSum = 0
        cur_arr = []
        ans = []
        seen = set()

        def bt(i,curSum):
            nonlocal cur_arr, ans
            if curSum == target:
                ##print("in if: ", cur_arr, ans)
                if tuple(cur_arr) not in seen:
                    seen.add(tuple(cur_arr))
                    ans.append(cur_arr[:])
                return
            if i == len(candidates) or curSum > target:
                return

            curSum += candidates[i]
            cur_arr += [candidates[i]]
            bt(i, curSum)
            curSum -= candidates[i]
            cur_arr.pop()

            curSum += candidates[i]
            cur_arr += [candidates[i]]
            #print(cur_arr)
            bt(i + 1, curSum)
            curSum -= candidates[i]
            cur_arr.pop()

            bt(i + 1, curSum)

        bt(0, curSum)
        return ans