LeetCode39. sum of combinations

Title Narrative:

Given an array of candidates with no repeated elements and a target, find all combinations of candidates that sum to the target.

The numbers in the candidates can be repeated indefinitely.

Description:

All numbers (including target) are positive integers.
The solution set cannot contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
The set of solutions sought is: [ [7], [2,2,3] ]

Example 2:

Input: candidates = [2,3,5], target = 8,
The set of solutions is: [ [2,2,2,2,2], [2,3,3], [3,5] ]

Thoughts:

The question mentions that the same number can be selected indefinitely, so we think, what if there are zeros in this array? Isn't that an infinite number of choices? But we see that the title says, all the numbers are positive integers, so we are relieved, we can first draw a recursive search tree to visualize the process of our question

39.组合总和

Note: This figure applies theCode Randomizerof the original image, readers who want a more in-depth look can check out the original author's article:
[Code Randomizer ()]()

1. Backtracking function parameters and return values

We need a one-dimensional array path to hold all the elements on the current path, and a two-dimensional array result to hold all the results.
A target value targetSum needs to be passed in, which is the sum of our target and the
And we need a sum to record the sum of all the elements of the current path, in fact, this is not necessary, we can add or subtract targetSum to achieve. But here we introduce the use of sum method, so more intuitive!

2. Abort condition for recursion

Note the return condition for the leaf nodes in the graph, since there is no number of combinations required for this problem, just a limit on the sum, there is no limit on the number of levels of recursion, as long as the sum of the selected elements exceeds the target, it returns!

//(coll.) fail (a student)sum≥targetSumIt's ready to go back.
if(sum>=targetSum){
    if(sum==targetSum) result.push_back(path);
    return;
}

3. Logic of single-level recursion

We control the horizontal traversal through the for loop, through the control of the recursive function to achieve vertical traversal, but here the vertical traversal can not be i + 1, but i, here must think clearly, because this question says an element can be repeated selection!!!! So that the vertical traversal, it is possible to include the current traversal of the elements in the code embodied in the recursive function parameter startindex == i, rather than i + 1.
Once we understand this, it's not hard to write the code:

        for(int i=startindex;i<();i++){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            // Here it's i, not i+1, because the same element can be fetched repeatedly
            backtracking(candidates,targetSum,sum,i).
            sum-=candidates[i];
            path.pop_back();
        }

Here we can also hide the backtracking process, the code is more concise, but beginners do not recommend this way of writing

        for(int i=startindex;i<();i++){
            path.push_back(candidates[i]);
            //Hiding backtracking in recursive functions
            backtracking(candidates,targetSum,sum+candidates[i],i);
            path.pop_back();
        }

Code:

With the above analysis, it is not difficult to come up with the code:

class Solution {
public:
    vector<int> path;
    vector<vector<int> > result;
    void backtracking(vector<int> candidates,int targetSum,int sum,int startindex){
        if(sum>=targetSum){
            if(sum==targetSum) result.push_back(path);
            return;
        }
        for(int i=startindex;i<();i++){
            //utilizationsumAdding and subtracting is more intuitive，It can also be hidden in the backtrace function。
            sum+=candidates[i];
            path.push_back(candidates[i]);
            //Here it is.i，is noti+1，Because the same element can be fetched repeatedly
            backtracking(candidates,targetSum,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ();();
        if(()==0) return result;
        backtracking(candidates,target,0,0);
        return result;
    }
};