class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // write your code here
        set<int> removeDuplicates(candidates.begin(), candidates.end());
        vector<int> nums(removeDuplicates.begin(), removeDuplicates.end());
        sort(nums.begin(), nums.end());

        vector<vector<int> > results;
        if (candidates.size() == 0) {
            return results;
        }
        vector<int> soFar;
        dfsHelper(nums, 0, soFar, target, results);
        return results;
    }

    // 1. 递归的定义： 在nums中，从startIndex起，选出剩余元素中的和等于remainTarget的子集，放入到soFar里；
    void dfsHelper(vector<int>& nums, int startIndex, vector<int> soFar, int remainTarget, vector<vector<int> >& results) {
        // 3. 递归的出口：当remainTarget为零的时候，停止对下一个元素的搜索；因为所有元素均为正数；
        if (remainTarget == 0) {
            results.push_back(soFar);
            return;
        }


        // 2. 递归的拆解：exhaust子集中第一个元素的choice，基于第一个元素的选择，delegate对其余元素的选择给recursive function；每次找到第一个元素为首的所有集合后，在更换第一个元素之前，要remove之前对第一个元素的选择；
        for (int i = startIndex; i < nums.size(); i++) {
            if (nums[i] > remainTarget) {
                break;
            }
            //[1] -> [1,2]
            soFar.push_back(nums[i]);
            // Since the same element from num nums[i] can be selected as many times as needed, the dfsHelper searching for the remaining elements would start from the same index i;
            dfsHelper(nums, i, soFar, remainTarget - nums[i], results);
            //[1,2] -> [1]
            soFar.pop_back();
        }

        return;
    }
};