力扣 77. 组合 & 39. 组合总和
77题目描述:
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
解析:
回溯法
Java:
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
backTrack(res, path, n, k, 1);
return res;
}
private void backTrack(List<List<Integer>> res, List<Integer> path, int n, int k, int index) {
if(path.size() == k) {
res.add(new ArrayList<Integer>(path));
return;
}
for(int i = index; i <= n; i++) {
path.add(i);
backTrack(res, path, n, k, i + 1);
path.remove(path.size() - 1);
}
}
}
JavaScript:
let res = [];
let path = [];
var combine = function(n, k) {
res = [];
backTrack(n, k, 1);
return res;
};
function backTrack(n, k, index) {
if(path.length === k) {
res.push([...path]);
return;
}
for(let i = index; i <= n; i++) {
path.push(i);
backTrack(n, k, i + 1);
path.pop();
}
}
39题目描述:
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
解析:
回溯法
Java:
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backTrack(res, path, candidates, target, 0, 0);
return res;
}
public void backTrack(List<List<Integer>> res, List<Integer> path, int[] candidates,
int target, int sum, int index) {
if(sum == target) {
res.add(new ArrayList<>(path));
return;
}
for(int i = index; i < candidates.length; i++) {
if(sum + candidates[i] > target) {
break;
}
path.add(candidates[i]);
backTrack(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1);
}
}
}
JavaScript:
var combinationSum = function(candidates, target) {
let res = new Array();
let path = new Array();
let sum = (arr) => { return arr.reduce((pre, cur)=> pre + cur,0) };
candidates.sort((a, b) => { return a - b; });
function dfs(index) {
if(sum(path) == target) {
res.push([...path]);
return;
}
for(let i = index; i < candidates.length; i++) {
path.push(candidates[i]);
if(sum(path) > target) {
path.pop();
break;
}
dfs(i);
path.pop();
}
}
dfs(0);
return res;
};