全排列问题解决
示例:
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
javascript
const permute = function(nums) {
const res = [];
const cur = [];
const len = nums.length;
// 校验是否被使用
const hash = {};
function dfs(num) {
if(num === len) {
// copy
res.push(cur.slice());
return;
}
for(let i = 0; i < len; i++ ) {
if(!hash[nums[i]]) {
hash[nums[i]] = 1;
cur.push(nums[i]);
dfs(num+1);
cur.pop();
hash[nums[i]] = 0
}
}
}
dfs(0);
console.log(res);
return res;
}
permute([1,2,3])
组合问题:变化的“坑位”,不变的“套路”
示例: 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
javascript
const subsets = function(nums) {
const res = [];
const cur = [];
const len = nums.length;
// 校验是否被使用
function dfs(num) {
res.push(cur.slice())
for(let i = num; i < len; i++) {
cur.push(nums[i]);
dfs(i+1);
cur.pop();
}
}
dfs(0);
console.log(res);
return res;
}
subsets([1,2,3])
限定组合问题:及时回溯,即为“剪枝”
示例: 输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
javascript
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
const combine = function(n, k) {
const res = [];
const cur = [];
function dfs(num) {
if(cur.length === k) {
res.push(cur.slice());
return;
}
for(let i = num; i < n; i ++) {
cur.push(i);
dfs(i+1);
cur.pop();
}
}
dfs(1);
return res;
}
combine(4,2)