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

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

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:

Enter: candidates = [2.3.6.7], target = 7Output: [[7], [2.2.3]]
Copy the code

Thinking: DFS

The end condition

  • When the recursive array is all recursive
  • When the sum of elements in the path is greater than the target value,
  • When the sum of the elements in the path > the target value, the path is thrown into the result array

If none of the recursive conditions are met, loop through the current array, enter DFS each time, assemble a new array (the contents of the array start at I of the current loop and end of the array) and pass in, and concatenate the new path

var combinationSum = function(candidates, target) {
  const res = []

  function dfs (arr, path) {
    if (arr.length === 0) {
      return
    }
    const currAdd = path.reduce((curr, add) = > curr + add, 0)
    if (currAdd > target) {
      return
    }
    if (currAdd === target) {
      res.push(path)
    }
    
    for (let i = 0; i < arr.length; i++) {
      dfs(arr.slice(i, arr.length), [...path, arr[i]]) 
      // Concatenate the new ARR, i-arr. length is to exclude the selected arR value. Concatenating new paths
    }
  }

  dfs(candidates, [], 0)

  return res
};

Copy the code

Optimization: DFS+ pruning

var combinationSum = function (candidates, target) {
    var resultList = [];
    var combin = function (value, path) {
        if (value === 0) return resultList.push(path.slice());

        if (value < 0) return;

        for (var i = 0; i < candidates.length; i++) {
            if (path.length === 0 || (path.length > 0 && path[path.length - 1] >= candidates[i])) {
                varminus = value - candidates[i]; path.push(candidates[i]); combin(minus, path); path.pop(candidates[i]); }}}; combin(target, []);return resultList;
};

Copy the code

Summary: added pruning, performance improved a lot ah.

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤