39. Combination Sum

39. Combination Sum

Medium

---

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

 

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

이 문제는 백트레킹 문제로 주어진 candidates를 이용해서 target을 만들 수 있는 조합( 중복 x )을 구하는 문제이다. 

중복을 방지하려면 반복문의 시작하는 위치를 나타내는 정수 변수 start를 전달해주면 된다.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const backtrack = (curr,total,start) => {
        if(total === target){
            ans.push([...curr])
            return
        }
        
        // 중복을 피하기위해 start를 시작으로 넘겨준다.
        for(let i=start; i<candidates.length; i++){
            const candidate = candidates[i]
            
            if(total + candidate > target) continue
            
            curr.push(candidate)
            backtrack(curr, total + candidate, i)
            curr.pop()
        }
        
    }
    
    const ans = [] 
    backtrack([],0,0)
    
    return ans 
};