This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.
53. The combination (combinations)
The label
- DFS + back
- medium
The title
Leetcode portal
Let’s just open leetCode.
Given two integers n and k, return 1… All possible combinations of k numbers in n.
Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the code
The relevant knowledge
Combination of problems, you can use the backtracking method: if you do not understand, please follow this backtracking idea
Basic steps
- Initialize the original array
- Using the old DFS + backtrace, the code is almost exactly the same as last time
- It’s different because you can’t rearrange it, so you add one
startIdx
Just under the limit
Writing implement
var combine = function(n, k) {
let [res, curUsed] = [[], {}]
N => nArray = [1, 2, 3, 4]
let nArray = new Array(n).fill(0).map((it, index) = > index + 1)
// DFS + backtrace
let dfs = (startIdx, curPath) = > {
if (curPath.length === k) {
res.push(curPath.slice())
return
}
for(let i = 0, len = nArray.length; i < len; i++){
if (curUsed[i] || i < startIdx) {
continue;
}
curPath.push(nArray[i])
curUsed[i] = true
dfs(i + 1, curPath)
curPath.pop()
curUsed[i] = false
}
}
dfs(0[]),return res
};
let n = 4, k = 2
console.log(combine(n, k))
Copy the code
54. The subset (subsets)
The label
- DFS + back
- medium
The title
Leetcode portal
Let’s just open leetCode.
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.
Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the code
Basic steps
I think you’ve read the above questions and understood. You know the steps of this question. Without further ado, the code is almost the same as above.
Writing implement
var subsets = function(nums) {
let [res, curUsed] = [[], {}]
let dfs = (startIdx, curPath) = > {
res.push(curPath.slice())
for(var i = 0, len = nums.length; i < len; i++){
if (curUsed[i] || i < startIdx) {
continue;
}
curPath.push(nums[i])
curUsed[i] = true
dfs(i + 1, curPath)
curPath.pop()
curUsed[i] = false
}
}
dfs(0[]),return res
};
let nums = [1.2.3]
console.log(subsets(nums))
Copy the code
55. Subsets II (Subsets II)
The label
- DFS + back
- medium
The title
Leetcode portal
Let’s just open leetCode.
Given an integer array nums that may contain repeating elements, return all possible subsets (power sets) of that array.
The solution set cannot contain duplicate subsets. You can return the solution set in any order.
,2,2 input: [1] output: [[2], [1],,2,2 [1], [2], [1, 2], []]Copy the code
Basic steps
An updated version of the previous question, with repeating elements. The general idea is the same, carefully read the comments below for minor changes.
Writing implement
var subsetsWithDup = function(nums) {
let [res, curUsed] = [[], {}]
/ / first order
nums = nums.sort((a, b) = > a - b)
let dfs = (startIdx, curPath) = > {
res.push(curPath.slice())
for(var i = 0, len = nums.length; i < len; i++){
if (curUsed[i] || i < startIdx) {
continue;
}
// The current value is used or
// The current value is equal to the previous value:
Nums [i-1] = nums[i-1]; nums[i-1] = nums[i-1]
// 2 nums[i-1] = nums[i-1] = nums[i-1
if (i > 0 && nums[i] === nums[i-1] && curUsed[i-1= = =false) {
continue
}
curPath.push(nums[i])
curUsed[i] = true
dfs(i + 1, curPath)
curPath.pop()
curUsed[i] = false
}
}
dfs(0[]),return res
};
let nums = [1.2.2]
console.log(subsetsWithDup(nums))
Copy the code
After these three questions, I think you have mastered the DFS + backtracking problem quite well!
In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series
That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions
In addition, want to talk to me, make a friend also welcome ha.