力扣00039.组合总和

发表于 分类于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 8 分钟
组合总和、数组、回溯、中等

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }
private:
    void backtrack(const vector<int>& candidates, int target, int start,
                   vector<int>& path, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i, path, result);
            path.pop_back();
        }
    }
};

结果

执行用时 : 3 ms, 击败 87.96% 使用 C++ 的用户

内存消耗 : 12.11 MB, 击败 40.40% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(candidates, target, 0, path, result);
        return result;
    }
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }
}

结果

执行用时 : 2 ms, 击败 82.50% 使用 Java 的用户

内存消耗 : 43.55 MB, 击败 28.62% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        result = []
        path = []
        def backtrack(start, target, path):
            if target == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                if candidates[i] > target:
                    continue
                path.append(candidates[i])
                backtrack(i, target - candidates[i], path)
                path.pop()
        backtrack(0, target, path)
        return result

结果

执行用时 : 30 ms, 击败 76.75% 使用 Python 的用户

内存消耗 : 11.51 MB, 击败 93.61% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        path = []
        def backtrack(start, target, path):
            if target == 0:
                result.append(path[:])
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                if candidates[i] > target:
                    continue
                path.append(candidates[i])
                backtrack(i, target - candidates[i], path)
                path.pop()
        backtrack(0, target, path)
        return result

结果

执行用时 : 46 ms, 击败 82.10% 使用 Python3 的用户

内存消耗 : 16.65 MB, 击败 30.56% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int candidatesSize_tmp;
int ansSize;
int combineSize;
int* ansColumnSize;

void backtrack(int* candidates, int target, int** ans, int* combine, int start) {
    if (target == 0) {
        int* tmp = malloc(sizeof(int) * combineSize);
        for (int i = 0; i < combineSize; ++i) {
            tmp[i] = combine[i];
        }
        ans[ansSize] = tmp;
        ansColumnSize[ansSize++] = combineSize;
        return;
    }
    for (int i = start; i < candidatesSize_tmp; ++i) {
        if (target - candidates[i] < 0) {
            continue;
        }
        combine[combineSize++] = candidates[i];
        backtrack(candidates, target - candidates[i], ans, combine, i);
        combineSize--;
    }
}
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    candidatesSize_tmp = candidatesSize;
    ansSize = combineSize = 0;
    int** ans = malloc(sizeof(int*) * 1001);
    ansColumnSize = malloc(sizeof(int) * 1001);
    int combine[2001];
    backtrack(candidates, target, ans, combine, 0);
    *returnSize = ansSize;
    *returnColumnSizes = ansColumnSize;
    return ans;
}

结果

执行用时 : 6 ms, 击败 94.16% 使用 C 的用户

内存消耗 : 9.00 MB, 击败 51.89% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);
        IList<IList<int>> result = new List<IList<int>>();
        IList<int> path = new List<int>();
        Backtrack(candidates, target, 0, path, result);
        return result;
    }
    private void Backtrack(int[] candidates, int target, int start, IList<int> path, IList<IList<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(path));
            return;
        }
        for (int i = start; i < candidates.Length; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            path.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

结果

执行用时 : 103 ms, 击败 91.01% 使用 C# 的用户

内存消耗 : 46.77 MB, 击败 19.10% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const path = [];
    function backtrack(start, target) {
        if (target === 0) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, target);
    return result;
};

结果

执行用时 : 67 ms, 击败 94.88% 使用 JavaScript 的用户

内存消耗 : 53.99 MB, 击败 13.71% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function combinationSum(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const result: number[][] = [];
    const path: number[] = [];
    function backtrack(start: number, target: number): void {
        if (target === 0) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, target);
    return result;
}

结果

执行用时 : 81 ms, 击败 55.52% 使用 TypeScript 的用户

内存消耗 : 54.88 MB, 击败 12.61% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {

    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        sort($candidates);
        $result = [];
        $path = [];
        $this->backtrack($candidates, $target, 0, $path, $result);
        return $result;
    }
    private function backtrack($candidates, $target, $start, &$path, &$result) {
        if ($target === 0) {
            $result[] = $path;
            return;
        }
        for ($i = $start; $i < count($candidates); $i++) {
            if ($i > $start && $candidates[$i] === $candidates[$i - 1]) {
                continue;
            }
            if ($candidates[$i] > $target) {
                continue;
            }
            $path[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i, $path, $result);
            array_pop($path);
        }
    }
}

结果

执行用时 : 15 ms, 击败 56.10% 使用 PHP 的用户

内存消耗 : 20.44 MB, 击败 7.32% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var candidates = candidates.sorted()
        var result: [[Int]] = []
        var path: [Int] = []
        backtrack(&candidates, target, 0, &path, &result)
        return result
    }
    private func backtrack(_ candidates: inout [Int], _ target: Int, _ start: Int, _ path: inout [Int], _ result: inout [[Int]]) {
        if target == 0 {
            result.append(path)
            return
        }
        for i in start..<candidates.count {
            if i > start && candidates[i] == candidates[i - 1] {
                continue
            }
            if candidates[i] > target {
                continue
            }
            path.append(candidates[i])
            backtrack(&candidates, target - candidates[i], i, &path, &result)
            path.removeLast()
        }
    }
}

结果

执行用时 : 7 ms, 击败 99.16% 使用 Swift 的用户

内存消耗 : 15.84 MB, 击败 5.88% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        val candidatesSorted = candidates.sorted().toIntArray()
        val result = mutableListOf<List<Int>>()
        val path = mutableListOf<Int>()
        backtrack(candidatesSorted, target, 0, path, result)
        return result
    }
    private fun backtrack(candidates: IntArray, target: Int, start: Int, path: MutableList<Int>, result: MutableList<List<Int>>) {
        if (target == 0) {
            result.add(ArrayList(path))
            return
        }
        for (i in start until candidates.size) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue
            }
            if (candidates[i] > target) {
                continue
            }
            path.add(candidates[i])
            backtrack(candidates, target - candidates[i], i, path, result)
            path.removeAt(path.size - 1)
        }
    }
}

结果

执行用时 : 232 ms, 击败 % 使用 Kotlin 的用户

内存消耗 : 39.69 MB, 击败 % 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  List<List<int>> combinationSum(List<int> candidates, int target) {
    List<List<int>> result = [];
    List<int> path = [];
    List<int> candidatesSorted = List.from(candidates)..sort();
    void backtrack(int start, int target) {
      if (target == 0) {
        result.add(List.from(path));
        return;
      }
      for (int i = start; i < candidatesSorted.length; i++) {
        if (i > start && candidatesSorted[i] == candidatesSorted[i - 1]) {
          continue;
        }
        if (candidatesSorted[i] > target) {
          continue;
        }
        path.add(candidatesSorted[i]);
        backtrack(i, target - candidatesSorted[i]);
        path.removeLast();
      }
    }
    backtrack(0, target);
    return result;
  }
}

结果

执行用时 : 319 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 146.83 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func combinationSum(candidates []int, target int) [][]int {
	var result [][]int
	var path []int
	sort.Ints(candidates)
	var backtrack func(start, target int)
	backtrack = func(start, target int) {
		if target == 0 {
			result = append(result, append([]int(nil), path...))
			return
		}
		for i := start; i < len(candidates); i++ {
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			if candidates[i] > target {
				continue
			}
			path = append(path, candidates[i])
			backtrack(i, target-candidates[i])
			path = path[:len(path)-1]
		}
	}
	backtrack(0, target)
	return result
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.61 MB, 击败 84.99% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
  result = []
  path = []
  candidates.sort!
  backtrack = lambda do |start, target|
    if target == 0
      result << path.dup
      return
    end
    (start...candidates.length).each do |i|
      next if i > start && candidates[i] == candidates[i - 1]
      next if candidates[i] > target
      path << candidates[i]
      backtrack.call(i, target - candidates[i])
      path.pop
    end
  end
  backtrack.call(0, target)
  result
end

结果

执行用时 : 67 ms, 击败 90.00% 使用 Ruby 的用户

内存消耗 : 206.49 MB, 击败 20.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
object Solution {
  def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
    var result: List[List[Int]] = List()
    var path: List[Int] = List()
    def backtrack(start: Int, target: Int): Unit = {
      if (target == 0) {
        result = path.reverse :: result
        return
      }
      for (i <- start until candidates.length) {
        if (i > start && candidates(i) == candidates(i - 1)) {
        } else if (candidates(i) <= target) {
          path = candidates(i) :: path
          backtrack(i, target - candidates(i))
          path = path.tail
        }
      }
    }
    candidates.sorted
    backtrack(0, target)
    result
  }
}

结果

执行用时 : 522 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 55.73 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
impl Solution {
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut path: Vec<i32> = Vec::new();
        let mut candidates_sorted = candidates.clone();
        candidates_sorted.sort();
        fn backtrack(
            candidates: &[i32],
            target: i32,
            start: usize,
            path: &mut Vec<i32>,
            result: &mut Vec<Vec<i32>>,
        ) {
            if target == 0 {
                result.push(path.clone());
                return;
            }
            for i in start..candidates.len() {
                if i > start && candidates[i] == candidates[i - 1] {
                    continue;
                }
                if candidates[i] > target {
                    continue;
                }
                path.push(candidates[i]);
                backtrack(candidates, target - candidates[i], i, path, result);
                path.pop();
            }
        }
        backtrack(&candidates_sorted, target, 0, &mut path, &mut result);
        result
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.03 MB, 击败 91.36% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户