Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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

The numbers in the candidates can be selected repeatedly without limit. Both combinations are unique if at least one of the selected numbers has a different number.

For a given input, there are fewer than 150 unique combinations of guaranteed and targets.

 

Example 1:

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

Example 2:

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

Example 3:

Input: Candidates = [2], target = 1

Example 4:

Input: Candidates = [1], Target = 1 output: [[1]]

Example 5:

Input: Candidates = [1], Target = 2 output: [[1,1]

 

Tip:

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidateEach element is unique.
  • 1 <= target <= 500

Their thinking

First, clarify the topic context:

  1. The number can be selected repeatedly
  2. Both the candidates and target are positive integers

Considering that [summation and solution are not repeated], I have experience with the sum of three numbers:

  1. The candidates must be sorted first
  2. Compare the current number with the number at the end of track to achieve the purpose of weight removal

Write special cases

  1. candidates.length<=0
  2. target<candidates[0]

Write the backTrack function, see the code

code

/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
// The numbers can be repeated and are all positive integers
var combinationSum = function(candidates, target) {
    let res=[]
    let len=candidates.length
    if(len<=0)return res

    candidates.sort((a,b) = >a-b)// Sort from smallest to largest

    if(candidates[0]>target)return res // Special arr[0]>target

    backTrack([],target)
    return res

    function backTrack(track,target){
        if(target===0) {// Termination conditions
            res.push(track.slice())
            return
        }

        for(let num of candidates){
            if(num>target){//target determines the value range
                break
            }

            [2,3] 【2,3,2
            if(track.length! = =0) {if(num>=track[track.length-1]) {// Determine whether this selection results in path duplication
                    track.push(num)
                    backTrack(track,target-num)
                    track.pop()
                }else{//continue
                    continue}}else{/ / track no elements
                track.push(num)
                backTrack(track,target-num)
                track.pop()
            }
            
        }
        
    }
};
Copy the code

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way