# 【算法】-回溯

## 集合的组合、排列

1. 所有子集

``````var helper = function (nums, index, subset, result) {
if (index == nums.length) {
result.push(subset.slice()); // 子集要深拷贝
} else if (index < nums.length) {
helper(nums, index + 1, subset, result);
subset.push(nums[index]);
helper(nums, index + 1, subset, result);
subset.pop();
}
};

var subsets = function (nums) {
let result = [];
if (nums.length == 0) return result;
helper(nums, 0, [], result);
return result;
};``````
``````var subsets = function (nums) {
const t = [];
const ans = [];
const n = nums.length;
const dfs = (cur) => {
if (cur === nums.length) {
ans.push(t.slice());
return;
}
t.push(nums[cur]);
dfs(cur + 1, nums);
t.pop(t.length - 1);
dfs(cur + 1, nums);
};
dfs(0, nums);
return ans;
};``````
1. 含有 k 个元素的组合

``````var helper = function (nums, index, subset, result, k) {
if (index == nums.length && subset.length == k) {
result.push(subset.slice()); // 子集要深拷贝
} else if (index < nums.length) {
helper(nums, index + 1, subset, result, k);
subset.push(nums[index]);
helper(nums, index + 1, subset, result, k);
subset.pop();
}
};

/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
let nums = new Array(n);
for (let i = 0; i < n; i++) {
nums[i] = i + 1;
}
let result = [];
if (nums.length == 0) return result;

helper(nums, 0, [], result, k);
return result;
};``````
1. 允许重复选择元素的组合

``````var helper = function (nums, index, subset, result, target) {
if (target == 0) {
result.push(subset.slice());
} else if (target > 0 && index < nums.length) {
helper(nums, index + 1, subset, result, target);
subset.push(nums[index]);
helper(nums, index, subset, result, target - nums[index]);
subset.pop();
}
};
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let result = [];
if (candidates.length == 0) return result;
helper(candidates, 0, [], result, target);
return result;
};``````
1. 包含重复元素集合的组合

``````var getNext = function (nums, index) {
let next = index;
while (next < nums.length && nums[next] == nums[index]) {
next++;
}
return next;
};

var helper = function (nums, index, subset, result, target) {
if (target == 0) {
result.push(subset.slice());
} else if (target > 0 && index < nums.length) {
helper(nums, getNext(nums, index), subset, result, target);
subset.push(nums[index]);
helper(nums, index + 1, subset, result, target - nums[index]);
subset.pop();
}
};

/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
let result = [];
if (candidates.length == 0) return result;
candidates.sort((a, b) => a - b);

helper(candidates, 0, [], result, target);
return result;
};``````
1. 没有重复元素集合的全排列

``````var swap = function (nums, i, j) {
if (i !== j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};

var helper = function (nums, i, result) {
if (i == nums.length) {
result.push(nums.slice());
} else {
for (let j = i; j < nums.length; j++) {
swap(nums, i, j);
helper(nums, i + 1, result);
swap(nums, i, j);
}
}
};

/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const result = [];
helper(nums, 0, result);
return result;
};``````
1. 含有重复元素集合的全排列

``````var swap = function (nums, i, j) {
if (i !== j) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};

var helper = function (nums, i, result) {
if (i == nums.length) {
result.push(nums.slice());
} else {
let map = new Map();
for (let j = i; j < nums.length; j++) {
if (!map.get(nums[j])) {
map.set(nums[j], true);
swap(nums, i, j);
helper(nums, i + 1, result);
swap(nums, i, j);
}
}
}
};

var permute = function (nums) {
const result = [];
helper(nums, 0, result);
return result;
};``````

## 使用回溯解决其他类型问题

1. 生成匹配的括号

``````var helper = function (left, right, parenthesis, result) {
if (left === 0 && right === 0) {
result.push(parenthesis);
return;
}
if (left > 0) {
helper(left - 1, n, parenthesis + "(", result);
}

if (left < right) {
helper(left, n - 1, parenthesis + ")", result);
}
};

var generateParenthesis = function (n) {
let result = [];
helper(n, n, "", result);
return result;
};``````
1. 分割回文子字符串

``````var isPalindrome = function (str, start, end) {
while (start < end) {
if (str.chatAt(start++) !== str.charAt(end--)) {
return false;
}
}
return true;
};

var helper = function (str, start, substrings, result) {
if (start === str.length) {
result.push(substrings.slice());
} else {
for (let i = start; i < str.length; i++) {
if (isPalindrome(str, start, i)) {
substrings.push(str.substring(start, i + 1));
helper(str, i + 1, substrings, result);
substrings.pop();
}
}
}
};

var partition = function (s) {
let result = [];
helper(s, 0, [], result);
return result;
};``````
1. 恢复 IP 地址

``````var isValidSeg = function(seg) {
return  Number(seg) <= 255 && (seg == "0" || seg.charAt(0) != '0')
}
var helper = function (s, i, segI, seg, ip, result) {
if (i == s.length && segI == 3 && isValidSeg(seg)) {
result.push(ip + seg);
} else if (i < s.length && segI <= 3) {
let ch = s.charAt(i)
if (isValidSeg(seg + ch)) {
helper(s, i+1, segI, seg + ch, ip, result)
}
if(seg.length > 0 && segI < 3) {
helper(s, i+1, segI + 1, "" + ch, ip + seg + ".", result)
}
}
};
var restoreIpAddresses = function (s) {
let result = [];
helper(s, 0, 0, "", "", result);
return result;
};``````