C++의 조합 합계 II

후보 번호 집합(모든 요소가 고유함)과 대상 번호가 있다고 가정합니다. 후보 번호가 주어진 목표와 합해지는 후보에서 모든 고유한 조합을 찾아야 합니다. 후보자 중에서 동일한 번호가 두 번 이상 선택되지 않습니다. 따라서 요소가 [2,3,6,7,8]이고 대상 값이 8이면 가능한 출력은 [[2,6],[8]]

단계를 살펴보겠습니다 -

• 재귀적으로 이것을 해결할 것입니다. 재귀 함수의 이름은 solve()입니다. 이것은 인덱스, 배열 a, 정수 b 및 다른 배열 temp를 취합니다. 해결 방법은 아래와 같이 작동합니다 -
• 빈 배열 res 정의
• b =0이면 res에 temp를 삽입하고 반환합니다.
• 인덱스 =크기인 경우 반환
• b <0이면 반환
• 배열 정렬
• 범위 인덱스에서 – 1의 크기에 대한 i
  • i> 인덱스이고 a[i] =a[i – 1]이면 계속
  • temp에 a[i] 삽입
  • 해결(i + 1, a, b – a[i], 온도)
  • temp에서 마지막 요소 삭제
• 인덱스 =0, 배열 a, 대상 b 및 다른 배열 temp를 전달하여 solve() 메서드 호출
• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]
8

출력

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