给定一个候选人编号的集合 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
方法一:排序 + 剪枝 + 回溯(两种写法)
我们可以先对数组进行排序,方便剪枝以及跳过重复的数字。
接下来,我们设计一个函数
在函数
我们也可以将函数
在主函数中,我们只要调用函数
时间复杂度
相似题目:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
ans.append(t[:])
return
if i >= len(candidates) or s < candidates[i]:
return
for j in range(i, len(candidates)):
if j > i and candidates[j] == candidates[j - 1]:
continue
t.append(candidates[j])
dfs(j + 1, s - candidates[j])
t.pop()
candidates.sort()
ans = []
t = []
dfs(0, target)
return ans
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
ans.append(t[:])
return
if i >= len(candidates) or s < candidates[i]:
return
x = candidates[i]
t.append(x)
dfs(i + 1, s - x)
t.pop()
while i < len(candidates) and candidates[i] == x:
i += 1
dfs(i, s)
candidates.sort()
ans = []
t = []
dfs(0, target)
return ans
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.add(new ArrayList<>(t));
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
for (int j = i; j < candidates.length; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
t.add(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.remove(t.size() - 1);
}
}
}
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.add(new ArrayList<>(t));
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
int x = candidates[i];
t.add(x);
dfs(i + 1, s - x);
t.remove(t.size() - 1);
while (i < candidates.length && candidates[i] == x) {
++i;
}
dfs(i, s);
}
}
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> t;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == 0) {
ans.emplace_back(t);
return;
}
if (i >= candidates.size() || s < candidates[i]) {
return;
}
for (int j = i; j < candidates.size(); ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
t.emplace_back(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.pop_back();
}
};
dfs(0, target);
return ans;
}
};
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> t;
function<void(int, int)> dfs = [&](int i, int s) {
if (s == 0) {
ans.emplace_back(t);
return;
}
if (i >= candidates.size() || s < candidates[i]) {
return;
}
int x = candidates[i];
t.emplace_back(x);
dfs(i + 1, s - x);
t.pop_back();
while (i < candidates.size() && candidates[i] == x) {
++i;
}
dfs(i, s);
};
dfs(0, target);
return ans;
}
};
func combinationSum2(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
cp := make([]int, len(t))
copy(cp, t)
ans = append(ans, cp)
return
}
if i >= len(candidates) || s < candidates[i] {
return
}
for j := i; j < len(candidates); j++ {
if j > i && candidates[j] == candidates[j-1] {
continue
}
t = append(t, candidates[j])
dfs(j+1, s-candidates[j])
t = t[:len(t)-1]
}
}
dfs(0, target)
return
}
func combinationSum2(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
cp := make([]int, len(t))
copy(cp, t)
ans = append(ans, cp)
return
}
if i >= len(candidates) || s < candidates[i] {
return
}
x := candidates[i]
t = append(t, x)
dfs(i+1, s-x)
t = t[:len(t)-1]
for i < len(candidates) && candidates[i] == x {
i++
}
dfs(i, s)
}
dfs(0, target)
return
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const t = [];
const dfs = (i, s) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
for (let j = i; j < candidates.length; ++j) {
if (j > i && candidates[j] === candidates[j - 1]) {
continue;
}
t.push(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.pop();
}
};
dfs(0, target);
return ans;
};
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const t = [];
const dfs = (i, s) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
const x = candidates[i];
t.push(x);
dfs(i + 1, s - x);
t.pop();
while (i < candidates.length && candidates[i] === x) {
++i;
}
dfs(i, s);
};
dfs(0, target);
return ans;
};
function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
for (let j = i; j < candidates.length; j++) {
if (j > i && candidates[j] === candidates[j - 1]) {
continue;
}
t.push(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.pop();
}
};
dfs(0, target);
return ans;
}
function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
const x = candidates[i];
t.push(x);
dfs(i + 1, s - x);
t.pop();
while (i < candidates.length && candidates[i] === x) {
++i;
}
dfs(i, s);
};
dfs(0, target);
return ans;
}
impl Solution {
fn dfs(i: usize, s: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if s == 0 {
ans.push(t.clone());
return;
}
if i >= candidates.len() || s < candidates[i] {
return;
}
for j in i..candidates.len() {
if j > i && candidates[j] == candidates[j - 1] {
continue;
}
t.push(candidates[j]);
Self::dfs(j + 1, s - candidates[j], candidates, t, ans);
t.pop();
}
}
pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut ans = Vec::new();
Self::dfs(0, target, &candidates, &mut vec![], &mut ans);
ans
}
}
impl Solution {
fn dfs(mut i: usize, s: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if s == 0 {
ans.push(t.clone());
return;
}
if i >= candidates.len() || s < candidates[i] {
return;
}
let x = candidates[i];
t.push(x);
Self::dfs(i + 1, s - x, candidates, t, ans);
t.pop();
while i < candidates.len() && candidates[i] == x {
i += 1
}
Self::dfs(i, s, candidates, t, ans);
}
pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut ans = Vec::new();
Self::dfs(0, target, &candidates, &mut vec![], &mut ans);
ans
}
}
public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int[] candidates;
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.Add(new List<int>(t));
return;
}
if (i >= candidates.Length || s < candidates[i]) {
return;
}
for (int j = i; j < candidates.Length; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
t.Add(candidates[j]);
dfs(j + 1, s - candidates[j]);
t.RemoveAt(t.Count - 1);
}
}
}
public class Solution {
private List<IList<int>> ans = new List<IList<int>>();
private List<int> t = new List<int>();
private int[] candidates;
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.Add(new List<int>(t));
return;
}
if (i >= candidates.Length || s < candidates[i]) {
return;
}
int x = candidates[i];
t.Add(x);
dfs(i + 1, s - x);
t.RemoveAt(t.Count - 1);
while (i < candidates.Length && candidates[i] == x) {
++i;
}
dfs(i, s);
}
}