39. Combination Sum

https://leetcode.com/problems/combination-sum/

Combination Sum - LeetCode

 

 

backtracking으로 푸는 문제

 

target에서 현재 candidates값을 빼주면서 음수가 되는 경우를 제외한다.

target이 0이 되면 조건을 충족한것이므로 최종리스트값에 더한다.

 

특이한 사항은 한번 쓴 숫자를 계속 써도 된다는 것이 포인트

 

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        
        
        def backtracking(start, res, path, target):
            
            #print(path)
            if target < 0:
                return
            
            if target == 0:
                res.append(path)
                
            for i in range(start, len(candidates), 1):
                
                backtracking(i, res, path + [ candidates[i]], target-candidates[i])
            pass
            return res
        
        candidates.sort()
        
        return backtracking(0, [], [], target)