Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 조합 합계 II(Combination Sum II) — 백트래킹으로 중복 없는 조합 찾기

문제 개요

서로 중복되지 않는 숫자들로 구성된 후보 배열과 하나의 목표 값(target)이 주어집니다. 이때 후보 숫자들을 조합하여 그 합이 목표 값과 일치하는 모든 고유한 조합을 찾아야 하며, 동일한 숫자를 두 번 이상 선택할 수는 없습니다.

예를 들어 후보 배열이 [2, 3, 6, 7, 8]이고 목표 값이 10이라면, 가능한 결과는 [[2, 8], [3, 7]]입니다.

해결 접근 방식: 백트래킹

이 문제는 재귀와 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 각 단계에서 숫자를 하나씩 선택해 보고, 목표 값을 초과하면 되돌아가 다른 경로를 탐색하는 것입니다. 또한 배열을 미리 정렬한 뒤 인접한 중복 원소를 건너뛰어 결과 조합의 중복을 방지합니다.

재귀 함수 solve()는 현재 인덱스(index), 후보 배열 a, 남은 목표 값 b, 그리고 지금까지 선택한 숫자를 담는 임시 배열 temp를 매개변수로 받으며, 다음과 같이 동작합니다.

  • 결과를 저장할 빈 배열 res를 준비합니다.
  • b가 0이면 temp를 res에 추가하고 종료합니다. (조합 완성)
  • index가 배열 a의 크기와 같으면 종료합니다.
  • b가 음수이면 종료합니다. (더 이상 진행 불가)
  • 배열 a를 오름차순으로 정렬합니다.
  • i를 index부터 배열 끝까지 반복하며 다음을 수행합니다.
    • i > index이고 a[i] == a[i-1]이면 건너뜁니다. (중복 조합 방지)
    • temp에 a[i]를 추가합니다.
    • solve(i + 1, a, b - a[i], temp)를 재귀 호출합니다.
    • 탐색이 끝나면 temp의 마지막 원소를 제거합니다. (백트래킹)
  • solve()를 index = 0, 배열 a, 목표 값 b, 빈 배열 temp로 호출합니다.
  • res를 반환합니다.

C++ 구현 코드

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
  public:
    vector < vector <int> > res;
void solve(int idx, vector <int> &a, int b, vector <int> temp){
        if(b == 0){
            res.push_back(temp);
            return;
        }
        if(idx == a.size())return;
        if(b < 0)return;
        sort(a.begin(), a.end());
        for(int i = idx; i < a.size(); i++){
            if(i > idx && a[i] == a[i-1])continue;
            temp.push_back(a[i]);
            solve(i + 1, a, b - a[i], temp);
            temp.pop_back();
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &a, int b) {
        res.clear();
        vector <int> temp;
        solve(0, a, b, temp);
        return res;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,3,6,7,8};
    print_vector(ob.combinationSum2(v, 10)) ;
}

실행 결과

입력:

[2,3,6,7,8]
10

출력:

[[2, 8],[3, 7]]

복잡도 분석

  • 시간 복잡도: O(2N) — 각 원소마다 '선택' 또는 '건너뛰기' 두 가지 경우가 존재하므로, 최악의 경우 지수 시간이 소요됩니다.
  • 공간 복잡도: O(N) — 재귀 호출 스택과 임시 배열 temp가 재귀 깊이에 비례하여 메모리를 사용합니다.

마무리

조합 합계 II 문제는 백트래킹의 대표적인 활용 사례입니다. 정렬을 활용해 중복 조합을 효율적으로 제거하고, 재귀적으로 모든 경우를 탐색하는 이 패턴은 부분 집합(subset), 순열(permutation) 등 다양한 조합형 문제에도 그대로 응용할 수 있으므로 꼭 익혀두시기 바랍니다.