// Combination Sum II

// 时间复杂度O(n!)，空间复杂度O(n)

class Solution {

public:

vector<vector<int> > combinationSum2(vector<int> &nums, int target) {

sort(nums.begin(), nums.end()); // 跟第 50 行配合，

// 确保每个元素最多只用一次

vector<vector<int> > result;

vector<int> path;

dfs(nums, path, result, target, 0);

return result;

}

private:

// 使用nums[start, nums.size())之间的元素，能找到的所有可行解

static void dfs(const vector<int> &nums, vector<int> &path,

vector<vector<int> > &result, int gap, int start) {

if (gap == 0) { // 找到一个合法解

result.push_back(path);

return;

}

int previous = -1;

for (size_t i = start; i < nums.size(); i++) {

// 如果上一轮循环已经使用了nums[i]，则本次循环就不能再选nums[i]，

// 确保nums[i]最多只用一次

if (previous == nums[i]) continue;

if (gap < nums[i]) return; // 剪枝

previous = nums[i];

path.push_back(nums[i]);

dfs(nums, path, result, gap - nums[i], i + 1);

path.pop_back(); // 恢复环境

}

}

};