The main application scenarios are some situations that need to be enumerated. Here is the exercise record that follows the booklet, including three intermediate questions of full permutation, subset and combination. Also, the syntax tree generator recommends :mshang.ca/syntree/
The whole arrangement【 Li Kou 46】
Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.
The sample
Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the codeTrain of thought
The thing to do is to fill in the nums.length positions with numbers, which can be represented by a tree, with each layer of the tree representing a position in the array. Rules to follow when filling in numbers:
- The number filled in is not filled in in the permutation, that is, each node cannot be the same as the ancestor
- Any number that hasn’t been filled in can be filled in here, which is the children of each node, and should include any number that isn’t its ancestor
- When all positions are filled in, the sorting is complete and the number is filled in. The depth of
nums.lengthIs the leaf node
Repeat the number filling operation using recursion as follows:
code
var permute = function(nums) {
const len=nums.length;
let visited={};// Map whether num is used in the current permutation
let curr=[];// Store the current array
let res=[];// Store the final result
let nth=0;/ / pit a number
var dfs=function(nth){
if(nth===len){// Reach the recursive boundary
res.push(curr.slice());// Put the current permutation into the permutation array
return;
}
for(let i=0; i<len; i++){if(! visited[nums[i]]){ visited[nums[i]]=1;// Unaccessed data is sorted and marked as accessed
curr.push(nums[i]);
dfs(nth+1);// Search for the next pit
curr.pop();// Make the pit space available to the next number
visited[nums[i]]=0;
}
}
}
dfs(nth);// Start traversal from the first position
return res;
};
Copy the codeUpgraded version: Full array ⅱPower button 47
Given a sequence nums that can contain repeating digits, return all non-repeating full permutations in any order.
The sample
Output: input: nums =,1,2 [1] [,1,2 [1], [1, 2, 1], [2,1,1]]Copy the codeAnalysis of the
As shown:
- The first pit is traversed
nums[1]Can not put into 1, will and intonum[0]Results of 1 are repeated - When the current queue is [1, NULL, NULL], the second pit can be placed
nums[1]Because thenums[0]Used in the first pit
Therefore, it is only necessary to ensure that unused repeated digits are used only once in the same pit to meet the requirement of non-repetition. Nums [I]=== NUMs [i-1]; nums[I]===nums[i-1
code
var permuteUnique = function(nums) {
const len=nums.length;
let visited=new Array(len).fill(false);// Map whether num is used in the current permutation, because nums contains repeated numbers, Map cannot be used
let curr=[];// Store the current array
let res=[];// Store the final result
let nth=0;/ / pit a number
var dfs=function(nth){
if(nth===len){// Reach the recursive boundary
res.push(curr.slice());// Put the current permutation into the permutation array
return;
}
for(let i=0; i<len; i++){if(visited[i]||(i>0&&nums[i]===nums[i-1] &&! visited[i-1])){// Skip: ① already arranged digits ② repeated digits
continue;
}
visited[i]=1;// Unaccessed data is sorted and marked as accessed
curr.push(nums[i]);
dfs(nth+1);// Search for the next pit
visited[i]=0;// Remove the current pit
curr.pop();
}
}
nums.sort((a,b) = >a-b);/ / sorting
dfs(nth);// Start traversal from the first position
return res;
};
Copy the codeA subset ofPower button 78
You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.
The solution set cannot contain duplicate subsets. You can return the solution set in any order.
The sample
Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the codeTrain of thought
Each number in numS can be in a subset and not in a subset, as shown below:
You go through each number, you keep going through what you put in that number and what you don’t put in that number, and each change is a new subset, you put in the solution set.
code
var subsets = function(nums) {
const subset = [];// The current subset
const len = nums.length
const res = [];// Set of subsets
const dps = function(index){
res.push(subset.slice());// Each time the index is passed, it changes to a different subset
for(leti=index; i<len; i++){ subset.push(nums[i]);// There are num[I] cases
dps(i+1);// Continue traversing;
subset.pop();// No nums[I]
}
}
dps(0);
return res;
};
Copy the codeUpgrade: Limit the composition problem【 Li Kou 77】
Given two integers n and k, return all possible combinations of k numbers in the range [1, n].
You can return the answers in any order.
The sample
Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the codeThe idea is to change the recursive bounds from the previous problem, only if the subset length is K, you need to push the array of results and not iterate down. (Pruning) code
var combine = function(n, k) {
const res=[];
const subset=[];
const dfs=function(num){
if(subset.length==k) {
res.push(subset.slice());
return;
}
for(leti=num; i<=n; i++){ subset.push(i); dfs(i+1);
subset.pop();
}
}
dfs(1);
return res;
};
Copy the codeRecursive and backtracking problem solving templates
function xxx(The ginseng) {
// Preparation of variable definition, cache, etc
// Define the path stack
const path = []
/ / into the DFSDFS (starting point)/ / define DFS
dfs(A recursive parameter) {
if{handle boundary logic in conjunction with questions, usually related to path contentreturn
}
for(Optional values for traversing the pit) {path.push(currently selected value) handles the associated logic of the pit itself path.pop()}}}Copy the code