Bactracking-1/combinationsum.py at master · veeceey/Bactracking-1 · 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
"""
https://leetcode.com/problems/combination-sum/
"""


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ###recursion

        #         self.result=[]
        #         if candidates is None:
        #             return result
        #         self.helper(candidates, 0, target, [])
        #         return self.result
        #     def helper(self, candidates, index, target, path):
        #         ##base case
        #         if target==0:
        #             self.result.append(path)
        #             return
        #         if target<0 or index>=len(candidates):
        #             return
        #         ##logic

        #         ##not chose
        #         self.helper(candidates, index+1, target, list(path))

        #         ##chose
        #         path.append(candidates[index])
        #         self.helper(candidates, index, target-candidates[index], list(path))

        ##backtrack

        self.result = []
        if candidates is None:
            return result
        self.helper(candidates, 0, target, [])
        return self.result

    def helper(self, candidates, index, target, path):
        ##base case
        if target == 0:
            self.result.append(list(path))
            return
        if target < 0 or index >= len(candidates):
            return
            ##logic

        ##not chose
        self.helper(candidates, index + 1, target, path)

        ##chose
        path.append(candidates[index])
        self.helper(candidates, index, target - candidates[index], path)
        path.pop()

    ##for loop based recursion