LeetCode39- Combinatorial summation

One 、 Title Description

Two 、 Topic analysis

2.1 Backtracking tree

Combinatorial problem is a typical problem that needs to be solved by backtracking algorithm , When dealing with backtracking algorithms , Think about the structure of the backtracking tree , And try to draw the backtracking tree of the problem , When drawing the backtracking tree , Pay attention to a special requirement in the title ： There is no limit to the same number , The following is an illustration of the backtracking tree （ With [2,3,6,7] For example ）：

2.2 Recursive termination condition

According to the title, it is easy to think of at least two termination conditions ：
（1） The sum on the current traversal path is equal to target When , Then collect the results , And no recursion at the next level
（2） The sum on the current traversal path is greater than target When , Then this path can be pruned directly , No recursion at the next level

3、 ... and 、 Basic code implementation

class Solution {
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> res = new ArrayList<>();
        solve(candidates, target, res, new ArrayList<>(), 0, 0);
        return res;
    }
    
    // curRes Store the nodes in the current path 
    // curSum Store the sum of the current path node 
    // res Used to collect all sequences that meet the conditions 
    public void solve(int[] candidates, int target, List<List<Integer>> res,List<Integer> curRes, int startIndex, int curSum) {
    
            if (curSum == target) {
    
                res.add(new ArrayList<>(curRes));
                return;
            }

            if (curSum > target) {
    
                return;
            }

            for (int i = startIndex; i < candidates.length; i += 1) {
    
                curSum += candidates[i];
                curRes.add(candidates[i]);
                solve(candidates, target, res, curRes, i, curSum);
                curSum -= candidates[i];
                curRes.remove(curRes.size() - 1);
            }
    }
}

Four 、 Further optimization

The two recursive termination conditions given above can only be regarded as the basic bound conditions of backtracking algorithm , Used to terminate recursion , But we don't give the pruning condition of backtracking algorithm ,curSum > target You can only cut the branches under the same path , You can't cut off branches on the same layer , In fact, in the process of backtracking , When we need to extend nodes of the same layer （ namely for In the cycle ）, If the nodes of the same layer are extended in ascending order （ Just sort the original array in ascending order ）, Then we can also prune , The condition for pruning is still curSum > target, The optimized code is as follows ：

class Solution {
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        solve(candidates, target, res, new ArrayList<>(), 0, 0);
        return res;
    }

    /** *  Solve the combinatorial summation problem by backtracking algorithm  * * @param candidates * @param target * @param res  Store all results that meet the conditions  * @param curRes  Store the results that meet the conditions in the current search path  * @param startIndex  The index at the beginning of each layer  */
    public void solve(int[] candidates, 
        int target, List<List<Integer>> res, 
        List<Integer> curRes, int startIndex, int curSum) {
    
            if (curSum == target) {
    
                res.add(new ArrayList<>(curRes));
                return;
            }

            if (curSum > target) {
    
                //  Only the branches under the same path can be cut here 
                return;
            }

            for (int i = startIndex; i < candidates.length; i += 1) {
    
                curSum += candidates[i];
                if (curSum > target) {
    
                    //  Cut off the branches of the same layer , namely for The loop is no longer extended 
                    break;
                }
                curRes.add(candidates[i]);
                solve(candidates, target, res, curRes, i, curSum);
                curSum -= candidates[i];
                curRes.remove(curRes.size() - 1);
            }
    }
}

5、 ... and 、 Submit results