40. Combination Sum II

---

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

Combination Sum II - LeetCode

 

임의의 정수 목록과 목표 값이 주어졌을 때, 목록의 요소들의 합으로 목표 값을 만족하는 결과 목록을 출력하는 문제다.

2021.11.07 - [코딩테스트 준비/leetcode] - 39. Combination Sum와 비슷한 유형이지만 차이점이 있는데

주요 고민 포인트는 다음과 같은 3가지다.

1. 주어지는 목록이 unique하지 않음

2. 주어지는 목록의 요소를 1번씩만 사용해야함

3. 결과 목록에서 중복이 있으면 안됨

---

class Solution {
public:
    void solve(vector<int>& candidates, int index, int target, std::vector<std::vector<int>>& ret, vector<int>& sub_ret) {
        if (target == 0)
        {
            sort(sub_ret.begin(), sub_ret.end());
            ret.push_back(sub_ret);
            return;
        }

        for (int i = index; i < candidates.size() && target >= candidates[i]; ++i)
        {
            // point3. 결과에 동일한 숫자가 들어가지 않게 하기 위해 중복 사용을 방지. (처음 사용되는 숫자를 제외하곤 동일하면 건너뛴다)
            if (i > index && candidates[i] == candidates[i-1])
                continue;
            
            if (target - candidates[i] < 0)
                break;
            
            sub_ret.push_back(candidates[i]);
            // point2. 동일한 요소를 2번 사용해서는 안된다
            solve(candidates, i + 1, target - candidates[i], ret, sub_ret);
            sub_ret.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if (candidates.empty())
            return vector<vector<int>>();

        if (candidates.size() == 1 && candidates.at(0) == target)
            return vector<vector<int>> { candidates };

        std::sort(candidates.begin(), candidates.end());
        std::vector<std::vector<int>> ret;
        std::vector<int> sub_ret;

        solve(candidates, 0, target, ret, sub_ret);
        return ret;
    }
};

---