“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

39. Sum of combinations

The title

Given an array of integer candidates with no duplicate elements and a target integer target, find all the different combinations that the candidates can make number and target, and return them as a list. You can return these combinations in any order.

The same number in the candidates can be selected repeatedly without limit. The two combinations are different if at least one number is chosen differently.

For a given input, the number of different combinations of and for target is guaranteed to be less than 150.

Example 1

The candidates must be written in the form of "2 + 2 + 3". The candidates must be written in the form of "2 + 2 + 3". The candidates must be written in the form of "3 + 3". Note that 2 can be used more than once. 7 is another candidate. 7 is equal to 7. There are only two combinations.Copy the code

Example 2

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

Answer key

Backtracking + pruning

Candidates =[2,3,6,7],target= 7contenders =[2,3,6,7],target= 7contenders =[2,3,6,7],target=7

graph TD 0[7] --2--> 1[5] 0[7] --3--> 2[4] 0[7] --6--> 3[1] 0[7] --7--> 4[0] 1[5]--2--> 5[3] 1[5]--3--> 6[2] 1[5]--6--> 7 [1] [5] 1-7 8 [2] -- > 2 [4] - 2 - > 9 [2] [4] - 3-2 - > 10 [1] [4] 2-6 - > 11 [1] [4] 2-7 - > 12 [1] [3] 3-2 - > 13 [1] [1] 3-3 - > 14 [1] [2] 3-6 - > 15 [5] 3 [1] - [6] 7 -- > 16 [3] - 2-5 - > 17 [1] 5 [3] - 3 - > 18 [0] 5 [3] - 6 - > 19 [3] 5 [3] - 7 - > 20 [4] 6 [2] - 2 - > 21 [0] [2] - 3-6 - > 22 [1] [2] 6-6 - > 23 [4] [2] 6-7 - > 24 [5] and [2] - 2 - - > 25 [0] 9 [2] - 3 - > 26 [1] and [2] - 6 - > 27 [4] and [2] - 7 - > [1] and [5] 10-2 - > 29 [1] [1] 10-3 - > 30 [1] [2] 10-6 - > 10 [1] [5] 31-7 - > 32 [6]

It’s not finished. That’s what it means. Combined with the above analysis, enumerate array, the target value – array element as the target value of the next enumeration array; This is a very obvious recursion

By depth-first traversal, subtract the enumerated array elements from the target value until the target value is 000 or the array enumerates to the last digit; Stop traversal; And logs the path elements on the target value of 000 into the result array.

pruning

[2,2,3] [2,2,3] [2,2,3] [2,2,3] [2,3][2, 3] [2,3][2, 3] [2,3][2, 3] [2,3,2

graph TD 0[7] --2--> 1[5] 0[7] --3--> 2[4] 0[7] --6--> 3[1] 0[7] --7--> 4[0] 1[5] --2--> 5[3] 1[5] --3--> 6[2] 1[5] - 6 - > [1] [5] 1-7 of 7 - > 8 [2] [3] - 2-5 - > 9 [1] 5 [3] - 3 - > 10 [0] 5 [3] - 6 - > 11 [3] 5 [3] - 7 - > 12 [1] [4] 9-2 - > 13 [1] [1] 9-3 - > 14 [1] [2] 9-6-9 > 15 [5] [1] - [6] 6 7 -- > 16 [2] - 3 - > 17 [1] [2] 6-6 - > 18 [4] [2] - 7 - > 19 [5] [4] - 3-2 - > 20 [1] [4] 2-6 - > 2 [4] [2] 21-7 - > 22 20 [1] - [3] 3 - > 23 [1] [2] 20-6 - > 24 20 [1] - [5] 7 - > 25 [6] 3[1] --6--> 27[-5] 3[1] --7--> 28[-6]

The clipped picture is finished. Pruning requires sorting the array to record the current enumeration position, so that enumeration does not start at the left of the array, reducing the number of duplicate branches;

The complete code

var combinationSum = function (candidates, target) {
  candidates.sort((a, b) = > a - b)
  let result = []
  const len = candidates.length
  dfs([], target, 0)
  return result
  function dfs(path, t, idx) {
    if (t === 0) {
      const a = [].concat(path)
      result.push(a)
      return
    }
    for (let i = idx; i < len; i++) {
      const c = candidates[i]
      path.push(c)
      t - c >= 0 && dfs(path, t - c, i)
      path.pop()
    }
  }
}
Copy the code