Leetcode-39-total number of combinations

# LeetCode-39- Total number of combinations

Given an array without repeating elements candidates And a target number target , find candidates All can make numbers and target The combination of .

candidates The number in can be selected repeatedly without limit .

explain ：

• All figures （ Include target） Positive integers .
• A solution set cannot contain duplicate combinations .

Example 1：

 Input : candidates = [2,3,6,7], target = 7,
 The solution set is :
[
  [7],
  [2,2,3]
]

Copy

Example 2：

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

Copy

# Their thinking

Method 1、DFS+ to flash back ：

The problem of permutation , Generally, it is also a full permutation problem

This kind of problem can be traced + Recursive solution

The basic idea ：

• When target=7 when , Root node , Make branch selection
• When it comes to 0 Or negative numbers , It's the leaf node , Go back
• When it comes to 0 when , Save the result set , From the root node to the leaf node (0) The path of is one of the combinations of answers

At first, you must draw a recursive tree on the paper , Write the entire tree structure of the example , After understanding how to implement the most basic algorithm , According to the meaning of the question, we need to consider the problem that the results are not repeated , So we need to prune the tree

For example 1 in , Possible paths are [[2,2,3],[2,3,2],[3,2,2],[7]]

Only [[7],[2,2,3]], obviously , The reason for repetition is that the previously selected elements are considered in the deeper node values

Pruning process ：

• When searching , You need to set the subscript of the starting point start, Avoid selecting previously selected nodes

# Java Code

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

    public void backtrack(int[] candidates,int target,List<List<Integer>> res,int i,List<Integer> tmp_list){
        if(target<0) return;
        if(target==0){
            res.add(new ArrayList<>(tmp_list));
            return;
        }
        //  If start from 0 Start , Will traverse all arrays , Select duplicate , Record start Avoid repetition 
        for(int start=i;start<candidates.length;start++){
            if(target<0) break;
            tmp_list.add(candidates[start]);
            backtrack(candidates,target-candidates[start],res,start,tmp_list);
            tmp_list.remove(tmp_list.size()-1);
        }
    }
}

Copy