// Combination Sum

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

class Solution {

public:

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

sort(nums.begin(), nums.end());

vector<vector<int> > result; // 最终结果

vector<int> path; // 中间结果

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

return result;

}

private:

void dfs(vector<int>& nums, vector<int>& path, vector<vector<int> > &result,

int gap, int start) {

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

result.push_back(path);

return;

}

for (size_t i = start; i < nums.size(); i++) { // 扩展状态

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

path.push_back(nums[i]); // 执行扩展动作

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

path.pop_back(); // 撤销动作

}

}

};