This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

preface

Force buckle 39 combined sum is as follows:

Given an array of positive integers with no duplicate elements and a positive integer target, find all the unique combinations of digits in the candidates that can make the sum the target number.

The numbers in the candidates may be selected indefinitely. The two combinations are unique if at least one of the selected numbers differs in number.

For a given input, there are fewer than 150 unique combinations that guarantee that sum is target.

Example 1:

Input: candidates =,3,6,7 [2], target = 7 output: [[7], [2, 2, 3]]Copy the code

Example 2:

Input: candidates =,3,5 [2], target = 8 output: [,2,2,2 [2], filling [2], [3, 5]]Copy the code

Tip:

Each element in the candidate is unique

A, thinking

Find all the combinations in the array that sum to target.

There are two important pieces of information in the title:

  1. There are no duplicate elements in the array
  2. The values in the array can be selected repeatedly

Based on the above two information, there are two points to pay attention to when recursing:

  1. Since there are no duplicate elements in the array, there is no need to consider whether there are duplicate results in the result set when recursing
  2. Because the values in the array can be selected repeatedly, the starting point of the recursion should be the same as the starting point of the loop. Suppose the first element in the result is selected with a subscript1As a starting point, the second element also needs to be subscripted1As a starting point)

For example

The candidates = [2,3,6,7], target = 7

Tips: Traversal In left-to-right order, use the stack to store traversal paths

  1. Select the first element2At this time,2 < 7Elements,2Into the stack
  2. Recursion 1: Continue to select the first element2At this time,2 plus 2 is less than 7Elements,2Into the stack
  3. Recursion 2: Continue selecting the first element2At this time,2 + 2 + 2 is less than 7Elements,2Into the stack. The stack is2 -> 2 -> 2
  4. Recursion 3: Continue selecting the first element2At this time,(2 + 2 + 2 + 2) > 7, without pushing, and without recursion down
  5. Recursion 3: Continue to select the second and subsequent elements. Obviously no result is satisfied, so the stack is pushed out of the stack. The stack is2 - > 2, this layer of recursion ends
  6. Recursion 2: Continue selecting the second element3At this time,(2 + 2 + 3) == 7The first correct result was found[2, 2, 3]
  7. . , the recursion process of other results is similar to that of the first result
  8. Finally you can get the right result:(2, 2, 3], [7]

Second, the implementation

The implementation code

The implementation code is a little different from the idea:

In order to avoid traversing the stack to get the sum, the next recursivetargetSet totarget - candidates[i]If thetarget == 0It means that a correct result has been found

/** * Backtracking algorithm */
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> ret = new ArrayList<>();
    int len = candidates.length;
    if (len == 0)
        return ret;
    Stack<Integer> path = new Stack<>();
    dfs(candidates, 0, target, path, ret);
    return ret;
}

/** * Backtracking implementation *@paramThe candidate array is *@paramBegin Indicates the search position *@paramTarget Indicates the target value@paramThe path path *@paramRet result set */
private void dfs(int[] candidates, int begin, int target, Stack<Integer> path, List<List<Integer>> ret) {
    // Pruning: no branching when target is negative and 0
    if (target < 0)
        return;
    if (target == 0) {
        ret.add(new ArrayList<>(path));
    }

    // Start search from begin
    for (int i=begin; i<candidates.length; i++) {
        // Path to the stack
        path.push(candidates[i]);
        // The next search will start at I because the selection will be repeated
        dfs(candidates, i, target - candidates[i], path, ret);
        // Path out stackpath.pop(); }}Copy the code

The test code

public static void main(String[] args) {
    int[] nums = {2.3.6.7};
    new test().combinationSum(nums, 7);
}
Copy the code

The results of

Third, summary

Although this problem is written out, but the beat rate is not very ideal.

Have a look at the algorithm written by others, using the first sort + then pruning, can effectively reduce the number of recursion. (Very good idea, click like ~)

Thank you for seeing the end, it is my great honor to help you ~♥