Idea: in contains the problem’s solution space, according to the depth first search strategy, starting from the root node depth explore the solution space tree, when exploration to a node, to judge whether the node contains problem solution, if included, from the node trigger continue to explore, if does not contain the solution of node, is back to its ancestor nodes one by one.

The sample

Combination sum: Given an array of no duplicate elements and a target number, find all combinations of the candidates that can be the sum of the number as target.

The numbers in the candidates can be selected repeatedly without limit.

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

Assume that the input data is the candidates = [2,3,5] and target = 8. The following preliminary analysis can be made:

  1. It can be picked indefinitely, like four twos
  2. To find all combinations, it means to explore all possible scenarios exhaustively
  3. When the data itself is greater than 8 or the sum is already greater than 8, there is no need to explore the following data

Referring to the idea of backtracking method: according to the depth-first rule, the definition of “depth” here starts from the first element, because it can be selected without limit, so it can be accumulated until it will exceed the target value, and then backtracking

Nodes exceeding the target value are removed

  • Pick the first element first and repeat, which is to go deeper and deeper

  • When the conditions are met, backtracking is performed

  • You can calculate that it doesn’t add up to 8, and keep going back

  • The sum of the current branch is still less than 8, so you can explore further

  • If the conditions are not met, backtrack

  • Still not satisfied with the condition that sum is 8, continue to backtrack

  • And less than 8 can continue to explore further along this branch and find a solution that satisfies the condition

  • It is not enough to just start the next branch attempt, so you can go back to the next node

After the new head node, continue to follow the depth-first principle

Code implementation

Public List<List<Integer>> combinationSum(int[] arguments, int target) {// The combinationSum(int[] arguments, int target) { List<List<Integer>> rs = DST (0,target, script);return rs;
    }
    public List<List<Integer>> dst(int start,int target,int[] candidates){
        List<List<Integer>> rs = new ArrayList<>(); 
       for(int i=start; i<candidates.length; i++){ int v=candidates[i];if(v>target){
               break; // Stop exploring}else  if(v==target){// Add rs.add(arrays.asList (v)); }elseList<List<Integer>> sc= DST (I,target-v, contenders);for(List<Integer> s:sc){List<Integer> f = new ArrayList<>(); f.add(v); f.addAll(s); rs.add(f); }}}return rs;
    }
Copy the code

The appendix

Summary of retrospective thinking