力扣00040.组合总和 II

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

题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2：

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

提示：

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

解决方法

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>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }
private:
    void backtrack(const vector<int>& candidates, int target, int start,
                   vector<int>& current, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(current);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.pop_back();
        }
    }
};

结果

执行用时 : 4 ms, 击败 86.36% 使用 C++ 的用户

内存消耗 : 12.34 MB, 击败 35.00% 使用 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>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        List<Integer> current = new ArrayList<>();
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    private void backtrack(int[] candidates, int target, int start,
                           List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

结果

执行用时 : 3 ms, 击败 66.48% 使用 Java 的用户

内存消耗 : 42.18 MB, 击败 53.22% 使用 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
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        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+1, target-candidates[i], path)
                path.pop()
        result = []
        candidates.sort()
        backtrack(0, target, [])
        return result

结果

执行用时 : 39 ms, 击败 59.84% 使用 Python 的用户

内存消耗 : 11.57 MB, 击败 85.09% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        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+1, target-candidates[i], path)
                path.pop()
        result = []
        candidates.sort()
        backtrack(0, target, [])
        return result

结果

执行用时 : 34 ms, 击败 98.78% 使用 Python3 的用户

内存消耗 : 16.48 MB, 击败 40.06% 使用 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
42
/**
 * 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 compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
void backtrack(int* candidates, int candidatesSize, int target, int start, int* path, int pathSize, int** result, int* returnSize, int** returnColumnSizes) {
    if (target == 0) {
        result[*returnSize] = (int*)malloc(pathSize * sizeof(int));
        for (int i = 0; i < pathSize; ++i) {
            result[*returnSize][i] = path[i];
        }
        (*returnColumnSizes)[*returnSize] = pathSize;
        (*returnSize)++;
        return;
    }
    for (int i = start; i < candidatesSize; ++i) {
        if (i > start && candidates[i] == candidates[i - 1]) {
            continue;
        }
        if (candidates[i] > target) {
            continue;
        }
        path[pathSize++] = candidates[i];
        backtrack(candidates, candidatesSize, target - candidates[i], i + 1, path, pathSize, result, returnSize, returnColumnSizes);
        pathSize--;
    }
}
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    int capacity = 1000;
    int** result = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));
    *returnSize = 0;
    int* path = (int*)malloc(candidatesSize * sizeof(int));
    int pathSize = 0;
    qsort(candidates, candidatesSize, sizeof(int), compare);
    backtrack(candidates, candidatesSize, target, 0, path, pathSize, result, returnSize, returnColumnSizes);
    free(path);
    return result;
}

结果

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

内存消耗 : 8.56 MB, 击败 63.44% 使用 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>> CombinationSum2(int[] candidates, int target) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> current = new List<int>();
        Array.Sort(candidates);
        Backtrack(candidates, target, 0, current, result);
        return result;
    }
    private void Backtrack(int[] candidates, int target, int start, List<int> current, IList<IList<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = start; i < candidates.Length; ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            current.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

结果

执行用时 : 109 ms, 击败 71.58% 使用 C# 的用户

内存消耗 : 46.38 MB, 击败 13.69% 使用 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 combinationSum2 = function(candidates, target) {
    let result = [];
    let current = [];
    candidates.sort((a, b) => a - b);
    function backtrack(start, target) {
        if (target === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            current.push(candidates[i]);
            backtrack(i + 1, target - candidates[i]);
            current.pop();
        }
    }
    backtrack(0, target);
    return result;
};

结果

执行用时 : 75 ms, 击败 47.12% 使用 JavaScript 的用户

内存消耗 : 52.57 MB, 击败 15.22% 使用 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 combinationSum2(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    const current: number[] = [];
    candidates.sort((a, b) => a - b);
    function backtrack(start: number, target: number): void {
        if (target === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                continue;
            }
            current.push(candidates[i]);
            backtrack(i + 1, target - candidates[i]);
            current.pop();
        }
    }
    backtrack(0, target);
    return result;
}

结果

执行用时 : 76 ms, 击败 56.86% 使用 TypeScript 的用户

内存消耗 : 53.46 MB, 击败 11.11% 使用 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 combinationSum2($candidates, $target) {
        $result = [];
        $current = [];
        sort($candidates);
        $this->backtrack($candidates, $target, 0, $current, $result);
        return $result;
    }
    private function backtrack($candidates, $target, $start, &$current, &$result) {
        if ($target === 0) {
            $result[] = $current;
            return;
        }
        for ($i = $start; $i < count($candidates); ++$i) {
            if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
                continue;
            }
            if ($candidates[$i] > $target) {
                continue;
            }
            $current[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i + 1, $current, $result);
            array_pop($current);
        }
    }
}

结果

执行用时 : 18 ms, 击败 61.54% 使用 PHP 的用户

内存消耗 : 20.05 MB, 击败 23.08% 使用 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 combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        var current: [Int] = []
        let sortedCandidates = candidates.sorted()
        func backtrack(_ start: Int, _ target: Int) {
            if target == 0 {
                result.append(current)
                return
            }
            for i in start..<sortedCandidates.count {
                if i > start && sortedCandidates[i] == sortedCandidates[i - 1] {
                    continue
                }
                if sortedCandidates[i] > target {
                    continue
                }
                current.append(sortedCandidates[i])
                backtrack(i + 1, target - sortedCandidates[i])
                current.removeLast()
            }
        }
        backtrack(0, target)
        return result
    }
}

结果

执行用时 : 6 ms, 击败 92.86% 使用 Swift 的用户

内存消耗 : 15.69 MB, 击败 9.52% 使用 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 combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()
        val sortedCandidates = candidates.sorted()
        fun backtrack(start: Int, target: Int) {
            if (target == 0) {
                result.add(current.toList())
                return
            }
            for (i in start until sortedCandidates.size) {
                if (i > start && sortedCandidates[i] == sortedCandidates[i - 1]) {
                    continue
                }
                if (sortedCandidates[i] > target) {
                    continue
                }
                current.add(sortedCandidates[i])
                backtrack(i + 1, target - sortedCandidates[i])
                current.removeAt(current.size - 1)
            }
        }
        backtrack(0, target)
        return result
    }
}

结果

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

内存消耗 : 40.25 MB, 击败 7.69% 使用 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>> combinationSum2(List<int> candidates, int target) {
    List<List<int>> result = [];
    List<int> current = [];
    candidates.sort();
    void backtrack(int start, int target) {
      if (target == 0) {
        result.add(List<int>.from(current));
        return;
      }
      for (int i = start; i < candidates.length; ++i) {
        if (i > start && candidates[i] == candidates[i - 1]) {
          continue;
        }
        if (candidates[i] > target) {
          continue;
        }
        current.add(candidates[i]);
        backtrack(i + 1, target - candidates[i]);
        current.removeLast();
      }
    }
    backtrack(0, target);
    return result;
  }
}

结果

执行用时 : 338 ms, 击败 0.00% 使用 Dart 的用户

内存消耗 : 148.07 MB, 击败 66.67% 使用 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 combinationSum2(candidates []int, target int) [][]int {
    var result [][]int
    var current []int
    sort.Ints(candidates)
    var backtrack func(int, int)
    backtrack = func(start, target int) {
        if target == 0 {
            result = append(result, append([]int{}, current...))
            return
        }
        for i := start; i < len(candidates); i++ {
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            if candidates[i] > target {
                continue
            }
            current = append(current, candidates[i])
            backtrack(i+1, target-candidates[i])
            current = current[:len(current)-1]
        }
    }
    backtrack(0, target)
    return result
}

结果

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

内存消耗 : 2.33 MB, 击败 92.31% 使用 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_sum2(candidates, target)
    result = []
    current = []
    candidates.sort!
    backtrack = lambda do |start, target|
        if target == 0
            result << current.dup
            return
        end
        (start...candidates.length).each do |i|
            next if i > start && candidates[i] == candidates[i - 1]
            next if candidates[i] > target
            current << candidates[i]
            backtrack.call(i + 1, target - candidates[i])
            current.pop
        end
    end
    backtrack.call(0, target)
    result
end

结果

执行用时 : 74 ms, 击败 50.00% 使用 Ruby 的用户

内存消耗 : 206.58 MB, 击败 -% 使用 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 combinationSum2(candidates: Array[Int], target: Int): List[List[Int]] = {
    var result: List[List[Int]] = List()
    var current: List[Int] = List()
    val sortedCandidates = candidates.sorted
    def backtrack(start: Int, target: Int): Unit = {
      if (target == 0) {
        result = result :+ current
        return
      }
      for (i <- start until sortedCandidates.length) {
        if (i > start && sortedCandidates(i) == sortedCandidates(i - 1)) {
        } else if (sortedCandidates(i) <= target) {
          current = current :+ sortedCandidates(i)
          backtrack(i + 1, target - sortedCandidates(i))
          current = current.dropRight(1)
        }
      }
    }
    backtrack(0, target)
    result
  }
}

结果

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

内存消耗 : 60.58 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
34
impl Solution {
    pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut current: Vec<i32> = Vec::new();
        let mut sorted_candidates = candidates;
        sorted_candidates.sort();
        fn backtrack(
            start: usize,
            target: i32,
            current: &mut Vec<i32>,
            result: &mut Vec<Vec<i32>>,
            sorted_candidates: &Vec<i32>,
        ) {
            if target == 0 {
                result.push(current.clone());
                return;
            }
            for i in start..sorted_candidates.len() {
                if i > start && sorted_candidates[i] == sorted_candidates[i - 1] {
                    continue;
                }

                if sorted_candidates[i] > target {
                    continue;
                }
                current.push(sorted_candidates[i]);
                backtrack(i + 1, target - sorted_candidates[i], current, result, sorted_candidates);
                current.pop();
            }
        }
        backtrack(0, target, &mut current, &mut result, &sorted_candidates);
        result
    }
}

结果

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

内存消耗 : 2.00 MB, 击败 95.00% 使用 Rust 的用户

Racket

暂时未解决

1

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

暂时未解决

1

结果

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

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