(Medium #39) Combination Sum

Problem

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

My solution

class Solution(object):
    def combinationSum(self, candidates, target):                
        candidates.sort()
        res = []
        
        self.dfs(candidates, 0, target, [], res)
        
        return res
        
    def dfs(self, cand, start, target, path, res):
        if target < 0: # backtracking
            return 
        if target == 0:
            res.append(path)
            return
        for i in range(start, len(cand)):
            self.dfs(cand, i,  target-cand[i], path+[cand[i]], res)

Runtime: 116ms, Memory: 13.9MB

참고

class Solution(object):
    def summ(self, list1, list2):
        list1 += list2
        list3 = list1
        list3[0] += 2        return    def check(self):
        a = [5]
        b = [3]
        self.summ(a, b)
        return a

a = Solution()
re = a.check()

• 파아썬 함수에서 list형을 인자로 받으면, 포인터로 받게되는 것을기억
• 위의 결과를 예측해보자.