[LeetCode][Back Tracking] 39. Combination Sum

 

 

문제 링크

leetcode.com/problems/combination-sum/

Combination Sum - LeetCode

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.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

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.

 

 

 

문제 해석

문제를 해석해 보면..

주어진 candidates 중에서 중복을 허용하여 골라 더한 값이 target이 되는 집합들의 집합을 뽑아내는 문제이다.

 

여기서 체크해야 할 점은 중복 허용! 잘못 작성하게 되면 무한루프를 탈 수 있다는 점!

이점에 유의하여 target과 같아질 경우와 target보다 커질 경우 잘 빠져나오도록 작성하면 된다.

 

Back Tracking 기본 문제인 듯하다!

 

 

제출 코드

class Solution {
    
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        func(candidates, List.of(), target, 0, 0);
        return this.result;
    }
    
    private void func(int[] candidates, List<Integer> combination, int target, int idx, int sum) {
        if (sum == target) {
            this.result.add(combination);
            return;
        }
        if (sum > target) return;
        
        for (int i = idx; i < candidates.length; i++ ) {
            List<Integer> availableComb = new ArrayList<>(combination);
            availableComb.add(candidates[i]);
            func(candidates, availableComb, target, i, sum + candidates[i]);
        }
    }
}

 

 

 

제출 결과

 

오랜만에 알고리즘을 풀었는데 재밌군! (ㅋㅋ)

런타임이랑 메모리 사용 생각 안 하고 일단 풀어보았는데 앞으론 생각해보도록 하자아 뀻!

- mushroong

 

 

 

 

---