LeetCode Combination Sum II

LeetCode Combination Sum II

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

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

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

这题和之前的LeetCode Combination Sum很类似,但是要求同一个数字不能重复选,不过candidates里面可能会有重复的数字。所以策略就是在一个for循环里面判断数字是否重复,注意不能在递归里面判断所选数字是否重复,因为递归的时候是可以选相同数字的,比如样例的[1,1,6]。同时递归的时候传入当前下标的下一个下标。

完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				if (i != idx && candidates[i] == candidates[i - 1])continue; // i != idx
				sol.push_back(candidates[i]);
				work(ans, candidates, i + 1, sol, target - candidates[i]); // i + 1
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

本代码提交AC,用时10MS。

Leave a Reply

Your email address will not be published. Required fields are marked *