十五周算法訓練營——回溯算法
今天是十五周算法訓練營的第十周，主要講回溯算法專題。
解決一個回溯問題，實際上就是一個決策樹的遍歷過程，只需要思考三個問題：
- 路徑：也就是已經做出的選擇
- 選擇列表：也就是你當前可以做的選擇
- 結束條件：也就是到達決策樹底層，無法再做選擇的條件
全排列
給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以按任意順序 返回答案。
示例 1：
輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。
function permute(nums) {
const result = [];
/**
* 路徑：記錄到track中
* 選擇列表：不存在與nums中的哪些數
* 結束條件：當nums中的元素全部在track中出現
*/
const backtrack = (track, nums) => {
// 結束條件
if (track.length === nums.length) {
result.push([...track]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (track.includes(nums[i])) {
continue;
}
// 做選擇
track.push(nums[i]);
// 進入下一層
backtrack(track, nums);
// 取消選擇
track.pop();
}
};
const track = [];
backtrack(track, nums);
return result;
}
const nums = [1, 2, 3];
console.log(permute(nums));全排列II
給定一個可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列。
示例 1：
輸入：nums = [1,1,2] 輸出： [[1,1,2], [1,2,1], [2,1,1]]。
function permuteUnique(nums) {
const result = [];
/**
* 路徑：記錄到track中
* 選擇列表：當前沒有被訪問過，且前一個值若為相通知，且被訪問過
* 結束條件：全部值都被訪問了一遍
*/
const backtrack = (sortNums, track, visits) => {
if (track.length === sortNums.length) {
result.push([...track]);
return;
}
for (let i = 0; i < sortNums.length; i++) {
// i > 0 && nums[i] === nums[i - 1] && !visits[i - 1]
// 上述一行的判斷是當前值和前一個值相等，但是前一個值沒有被訪問過，表示前一個值不在該值路徑的上幾層，表示在同一層前面出現過，所以該值要跳過
if (visits[i] || (i > 0 && sortNums[i] === sortNums[i - 1] && !visits[i - 1])) {
continue;
}
// 做選擇
track.push(sortNums[i]);
visits[i] = 1;
// 選擇下一層
backtrack(sortNums, track, visits);
// 取消選擇
track.pop();
visits[i] = 0;
}
};
const track = [];
nums.sort((a, b) => a - b);
const visits = (new Array(nums.length)).fill(0);
backtrack(nums, track, visits);
return result;
}
const nums = [1, 1, 2];
console.log(permuteUnique(nums));N皇后
按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。
示例 1：
輸入：n = 4 輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解釋：如上圖所示，4 皇后問題存在兩個不同的解法。
// 該問題本質上和全排列問題差不多，決策樹上的每一層表示棋盤上的每一行，每個節點可以做出的選擇是在該行的任意一列放置一個皇后
function solveNQueens(n) {
const result = [];
// 判斷是否可以在[row, col]放置皇后
const isValid = (board, row, col) => {
// 判斷該列是否存在皇后
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') {
return false;
}
}
// 判斷左上方是否存在皇后沖突
let leftRow = row - 1;
let leftCol = col - 1;
while (leftRow >= 0 && leftCol >= 0) {
if (board[leftRow][leftCol] === 'Q') {
return false;
}
leftRow--;
leftCol--;
}
// 判斷右上是否存在皇后沖突
let rightRow = row - 1;
let rightCol = col + 1;
while (rightRow >= 0 && rightCol < n) {
if (board[rightRow][rightCol] === 'Q') {
return false;
}
rightRow--;
rightCol++;
}
return true;
};
/**
* 路徑：board中小于row的那些行都已經成功放置了皇后
* 選擇列表：第row行的所有列都是放置皇后的選擇
* 結束條件：row超過board的最后一行
*/
const backtrack = (board, row) => {
// 觸發結束條件
if (row === board.length) {
result.push(board.map(item => {
return item.join('');
}));
return;
}
for (let col = 0; col < n; col++) {
// 排除不合法的選擇
if (!isValid(board, row, col)) {
continue;
}
// 做選擇
board[row][col] = 'Q';
// 進行下一層
backtrack(board, row + 1);
// 取消選擇
board[row][col] = '.';
}
};
const board = new Array(n);
for (let i = 0; i < n; i++) {
board[i] = (new Array(n)).fill('.');
}
backtrack(board, 0);
return result;
}
const n = 4;
console.log(solveNQueens(n));組合總和
給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。
candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。
對于給定的輸入，保證和為 target 的不同組合數少于 150 個。
示例 1：
輸入：candidates = [2,3,6,7], target = 7 輸出：[[2,2,3],[7]] 解釋： 2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一個候選， 7 = 7 。 僅有這兩種組合。
function combinationSum(candidates, target) {
const result = [];
/**
* 路徑：記錄在track中
* 選擇列表：index及其之后的元素
* 結束條件：其和為target，則進行存儲，超過，則不存儲結束
*/
const backtrack = (sortNums, track, trackNum, index) => {
if (trackNum === target) {
result.push([...track]);
return;
} else if (trackNum > target) {
return;
}
for (let i = index; i < sortNums.length; i++) {
// 做選擇
track.push(sortNums[i]);
trackNum += sortNums[i];
// 進入下一層
backtrack(sortNums, track, trackNum, i);
// 取消選擇
track.pop();
trackNum -= sortNums[i];
}
};
const track = [];
let trackNum = 0;
candidates.sort((a, b) => a - b);
backtrack(candidates, track, trackNum, 0);
return result;
}
const candidates = [2,3,6,7];
const target = 7;
console.log(combinationSum(candidates, target));子集II
給你一個整數數組 nums ，其中可能包含重復元素，請你返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。返回的解集中，子集可以按 任意順序 排列。
示例 1：
輸入：nums = [1,2,2] 輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]。
function subsetsWithDup(nums) {
const result = [];
/**
* 路徑：記錄在track中
* 選擇列表：index及其之后的元素
* 結束條件：將結果進行存儲
*/
const backtrack = (sortNums, track = [], index = 0) => {
result.push([...track]);
for (let i = index; i < sortNums.length; i++) {
// 對于排序后相同的元素應該跳過
if (i > index && sortNums[i] === sortNums[i - 1]) {
continue;
}
// 做選擇
track.push(sortNums[i]);
// 進入下一層
backtrack(sortNums, track, i + 1);
// 取消選擇
track.pop();
}
};
const track = [];
nums.sort((a, b) => a - b);
backtrack(nums, track, 0);
return result;
}
const nums = [1, 2, 2];
console.log(subsetsWithDup(nums));遞增子序列
給你一個整數數組 nums ，找出并返回所有該數組中不同的遞增子序列，遞增子序列中 至少有兩個元素 。你可以按 任意順序 返回答案。
數組中可能含有重復元素，如出現兩個整數相等，也可以視作遞增序列的一種特殊情況。
示例 1：
輸入：nums = [4,6,7,7] 輸出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]。
function findSubsequences(nums) {
const result = [];
const backtrack = (track, start) => {
// 如果其長度大于等于2，則算一個子序列
if (track.length >= 2) {
result.push([...track]);
}
const map = new Map();
for (let i = start; i < nums.length; i++) {
// 判斷是否合法
// 同一層只能用一次
if (map.has(nums[i])) {
continue;
}
// 后一層比前一層大
if (nums[i] < track[track.length - 1]) {
continue;
}
map.set(nums[i], true);
// 做選擇
track.push(nums[i]);
// 進入下一層
backtrack(track, i + 1);
// 取消選擇
track.pop();
}
};
const track = [];
backtrack(track, 0);
return result;
}
const nums = [1, 2, 3 ,1,1,1,1];
console.log(findSubsequences(nums));
