Given an array of n integers (nums) and a target value (target), determine if there are x elements in nums such that x1 + x2 +… Is the value equal to target? Find all tuples that meet the condition and are not duplicated.

First of all,

So let’s simplify this problem to this subelement down here

  • X = 1 – > traversalnumsFind a value that satisfies that requirement, and then push it into the array, de-duplicating 
    let result = []
let hash = {} // Use hash to deduplicate the result
for(let i = 0, len = nums.length; i < len; i++){
    if(nums[i] === target && hash[nums[i]] === undefined) {
         result.push(nums[i])
         hash[nums[i]] = true}}return result
Copy the code
  • X =2 -> iterate twicenumsFind the combination of values that satisfy the requirement, and then push it into the array, de-duplicating 
    let result = []
let hash = {} // Use hash to deduplicate the result
️for(let i = 0, len = nums.length; i < len; i++){
    for(let j = 0; j < len; j++){
        if(nums[i] + nums[j] === target
          && hash[[nums[i], nums[j]]] === undefined
          && hash[[nums[j], nums[i]]] === undefined){
            hash[[nums[i], nums[j]]] = true
            result.push([nums[i], nums[j]])
        }
    }
}
return result
Copy the code

    You can also use key-value objects to reduce one loop

    let map = {}
for(let i = 0, len = nums.length; i < len; i++){
    if(map[target - nums[i]] ! = =undefined){
        result.push([nums[i], nums[map[target - nums[i]]]])
    } else{
        map[nums[i]] = i
    }
}
return result
Copy the code
  • X = 3 – > · · · · · · 
    for() {for() {for(){···}}}return result
Copy the code
  • · · · · · ·

That seems to solve the problem, but it doesn’t seem to be very clever. And if you take all the combinations that satisfy this requirement, you can’t do this layer by layer for loop without limiting the number of numbers in the combination.

The advanced

  • Sort + pointer

    This method is suitable for the optimization of two, three and four layers of loop. The specific idea is: first select a number in an array, and then initialize the pointer to iterate over the other numbers to find the conditions that meet.

    • We take x=3 as 🌰
    var threeSum = function(nums, target) {
  let result = [],
      len = nums.length
  if(len < 3) {return result // boundary processing
  }
  nums.sort((a, b) = > a - b) / / sorting
  // Set L and R after I and move them back when they are equal
  // It is guaranteed that each combination found is unique
  for(let i = 0; i < len ; i++){
      if(nums[i] === nums[i- 1]) continue / / to heavy
      let L = i + 1
      let R = len - 1
      while(L < R){
          let sum = nums[i] + nums[L] + nums[R]
          if(sum === 0){
              result.push([nums[i],nums[L],nums[R]])
              while (L<R && nums[L] === nums[L+1]) L++ / / to heavy
              while (L<R && nums[R] === nums[R- 1]) R-- / / to heavy
              L++
              R--
          }
          else if (sum < 0) L++
          else if (sum > 0) R--
      }
  }        
  return result
 }
Copy the code

  • back

    If the topic request the tuples of all meet the requirements and do not limit the length, we can use backtracking method to solve, specific idea is: the original array every number has two choices, that is when a good man or be a undercover,, that is to be selected and not selected, so we can move forward to build the binary tree traveled through find meet the requirements of a tuple.

    • The recursion is as follows: 
      var sum = function(nums, target) {
    let tempNums = nums.slice(),
        result = [],
        buffer = [],
        index = 0,
        hash = {}
    let _sum = (index, target) = > {
        if(target === 0&& buffer.length ! = =0){
            result.push(buffer.slice())
        }
        if(index === tempNums.length){
            return
        }
        buffer.push(tempNums[index]) / / selected
        _sum(index+1, target - tempNums[index])
        buffer.pop() / / don't choose
        _sum(index+1, target)
    }
    _sum(index, target)
    // go to return
    return result.filter(_= > {
        _.sort((a, b) = > a-b)
        if(hash[_] === undefined){
            hash[_] = true
            return_}})}Copy the code

The last

On the sum of x number of the problem on the chat here, if there is a mistake, please correct 👀