LeetCode 40. Combination Sum II

思路

递归？呵呵
需要判断两个解是否相等，目前没有什么好办法，从boost库里抄了个hash函数过来。

代码

class Solution {
private:
	vector<vector<int>> results;
	size_t hashOfIntVec(const vector<int>& vec) const {
		size_t seed = vec.size();
		for (auto& i : vec) {
			seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		}
		return seed;
	}
public:
	void subCombSum(vector<int>& candidates, int start, int target, vector<int>& path) {
		for (int i = start; i<candidates.size(); i++) {
			if (target - candidates[i] == 0) {
				//bingo!
				path.push_back(candidates[i]);
				vector<int> pathCopy(path);
				sort(pathCopy.begin(), pathCopy.end());
				size_t hashVal = hashOfIntVec(pathCopy);
				bool hasSame = false;
				for (int j = 0; j < results.size(); j++) {
					if (hashVal == hashOfIntVec(results[j])) {
						hasSame = true;
						break;
					}
				}
				if(!hasSame)
					results.push_back(pathCopy);
				path.erase(path.end() - 1);
			}
			else if (target - candidates[i] > 0) {
				path.push_back(candidates[i]);
				subCombSum(candidates, i + 1, target - candidates[i], path);
				path.erase(path.end() - 1);
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
	    vector<int> path;
		subCombSum(candidates, 0, target, path);
		return results;
	}
};