[LeetCode] 40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/description/?envType=daily-question&envId=2024-08-13

leetcode - Combination Sum II

문제 유형 : 백트래킹, dfs, 재귀

문제 난이도 : Medium

 

문제

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

 

후보자 번호들의 모음 candidates와 target 번호가 주어진다.

candidate들의 합이 target이 되는 모든 조합을 구하시오.

중복 조합은 구하지 않고, 각 후보자들은 최대 한 번씩만 쓰일 수 있습니다.

 

풀이

dfs + 백트래킹으로 해결할 수 있다.

오름차순 정렬 후, 재귀적으로 i번부터 시작하여 모든 부분조합을 만들어서 탐색시킨다.

 

중복 조합 제거를 위해, 이전 인덱스와 같은 번호인 경우, continue로 루프를 건너뛰게 했고,

의미없는 조합을 방지하기 위해 sum이 target을 넘는 순간, 루프를 그만두도록 하였다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int n;
    int target;
    vector<vector<int>> result;

public:
    void solve(int idx, int sum, vector<int>& combination, vector<int>& candidates) {
        if(sum == target) {
            result.push_back(combination);
            return;
        }

        for(int i = idx; i < n; i++) {
            if (i > idx && candidates[i] == candidates[i - 1]) continue;
            if (sum + candidates[i] > target) break;

            combination.push_back(candidates[i]);
            solve(i+1, sum + candidates[i], combination, candidates);
            combination.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        this->target = target;
        n = candidates.size();
        sort(candidates.begin(), candidates.end());
        vector<int> combination;
        solve(0, 0, combination, candidates);
        return result;
    }
};