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

  1. Initialize the original array
  2. Using the old DFS + backtrace, the code is almost exactly the same as last time
  3. It’s different because you can’t rearrange it, so you add onestartIdxJust 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.

reference