LeetCode (C/C++, Java) 39. Combination Sum

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

---

풀이

후보의 수가 적고, 특정 규칙을 찾을 수 없어 모든 경우를 탐색했다.

재귀로 순회하며 모든 경우를 확인한 후, target일 경우의 수 집합을 저장한다. 이 때 중복을 제외하기 위해 현재 원소의 인덱스를 함께 넘겨 해당 위치부터 순회하도록 구현했다.

---

C/C++ 코드

class Solution {
public:
    vector<vector<int>> combinations;

    void findCombinations(vector<int>& candidates, int& target, vector<int> nowCombination, int nowSum, int idx) {
        if (nowSum == target) {
            combinations.push_back(nowCombination);
            return;
        }
        
        // 현재 인덱스부터 탐색 후 다음 원소로 이동
        for (int i = idx; i < candidates.size(); i++) {
            if (nowSum + candidates[i] <= target) {
                nowCombination.push_back(candidates[i]);
                findCombinations(candidates, target, nowCombination, nowSum + candidates[i], i);
                nowCombination.pop_back();
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> nowCombination;
        findCombinations(candidates, target, nowCombination, 0, 0);
        return combinations;
    }
};

 

Java 코드

class Solution {

    static void findCombinations(List<List<Integer>> combinations, int[] candidates, int target, List<Integer> combi, int nowSum, int nowIdx){
        if (target == nowSum) {
            combinations.add(new ArrayList<>(combi));
            return;
        }

        for (int i = nowIdx; i < candidates.length; i++) {
            if (nowSum + candidates[i] <= target) {
                combi.add(candidates[i]);
                findCombinations(combinations, candidates, target, combi, nowSum + candidates[i], i);
                combi.remove(combi.size() - 1);
            }
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> combi = new ArrayList<>();    
        findCombinations(combinations, candidates, target, combi, 0, 0);
        return combinations;
    }
}