Problem: 39. 组合总和

题目描述

思路及解题方法

该问题是组合问题的一个变体，可以归纳为元素无重复可复选问题，其代码的实现几乎和组合问题一模一样，由于在组合问题中我们只需要利用一个变量在递归时将其加一再传输到回溯函数中可以保证元素不会重复，那么我们只需让那个变量不再加一而是直接传输到回溯函数中即可，但此时我们需要重新找一个变量来控制递归的结束不然递归会无限的执行下去，此时我们定义一个整形变量targetSum来记录决策路径上的元素值是否等于target，若等于则将当前的决策路径添加到结果集合中，若大于target则结束当前的递归

复杂度

时间复杂度:

$O(N\times 2^N)$;其中$N$为数组candidates的长度

空间复杂度:

$O(N)$

Code

class Solution {
    //Recode the result
    vector<vector<int>> res;
    //Recode decision path
    vector<int> track;
    //Recode the sum of decision path
    int trackSum = 0;
public:
    /**
     * Find the number of combinations equal to the target sum
     *
     * @param candidates An array of combinations to be selected
     * @param target The target number
     * @return vector<vector<int>>
     */
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        if (candidates.size() == 0) {
            return res;
        }
        backtrack(candidates, 0, target);
        return res;
    }

    /**
     * Implementation of backtracking function
     * 
     * @param nums An array of combinations to be selected
     * @param start Thr decision stage
     * @param target The target number
     */
    void backtrack(vector<int> &nums, int start, int target) {
        //Base case
        if (trackSum == target) {
            res.push_back(track);
            return;
        }
        
        if (trackSum > target) {
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            track.push_back(nums[i]);
            trackSum += nums[i];
            backtrack(nums, i, target);
            track.pop_back();
            trackSum -= nums[i];
        }
    }
};