leetcode-40번

1.  문제 링크

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

Combination Sum II - LeetCode

 

2.  접근법

1. candidates을 정렬한다.
2. candidates에 대해 모든 조합을 구한다.(전수조사)
   1. 이때 조합의 모든 원소의 sum도 들고다닌다. => sum이 target보다 커지면 backtracking하여 경우의 수를 줄인다,
   2. 또한, 연속해서 같은 값이 나오는 경우 skip한다.
      1. [1,1,1,1,2,3]의 경우 [1,1,1,1]에서 2개의 1을 선택하는 경우의 수는 4C2 = 4*3/2 = 6인데 뒤에 [2,3]입장에서는 이 6가지가 모두 동일하게 인식됨 => 따라서, 연속 값이 나오는 경우 다 조합을 확인하지 말고 skip하면 된다.
      2. 이렇게 하면 경우의 수도 많이 줄일 수 있고 중복 케이스도 자동으로 방지됨
      3. 처음에 이부분을 생각하지 못하여 시간초과가 발생했다.

         

3. 모든 조합을 구하는 과정에서 원소의 총 합 == target이 될 때 마다 정답 배열에 push한다.

 

3. 코드

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
	void init(vector<int>& candidates, vector<vector<int>>& ans) {
		ans.clear();
		sort(candidates.begin(), candidates.end());
	}


	void Combi(vector<int> c_Comb, int c_sum, int start,const vector<int>& candidates, const int& target, vector<vector<int>>& ans) {
		if (c_sum > target)
			return;

		if (c_sum == target) {
			ans.push_back(c_Comb);
			return;
		}
		for (int i = start; i < candidates.size(); i++) {
			if (i != start && candidates[i] == candidates[i - 1]) continue;
			c_Comb.push_back(candidates[i]);
			Combi(c_Comb, c_sum + candidates[i], i + 1, candidates, target, ans);
			c_Comb.pop_back();
		}
		
	}

public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		init(candidates, ans);
		Combi({}, 0, 0, candidates, target, ans);

		return ans;
	}
};