Original link: leetcode-cn.com/problems/co…

Answer:

The solution refers to LeetCode solution of 46. Full permutation, backtracking, JavaScript, detailed comments.

  1. Use DFS to generate all possible permutations.
  2. You need to use the used array to identify whether each value has been used, and the used index is the number to be sorted.
  3. Points to note in clearing state:
    • Since the subResult and Used variables are reused in each recursion, care needs to be taken to restore the current state after each recursion.
    • In order toInput: n = 4, k = 2For example, assuming the first-level recursion, subresults obtained each time after the for loop clears the state are respectively[1],[2],[3],[4], used are respectively[false, true, false, false, false],[false, false, true, false, false],[false, false, false, true, false],[false, false, false, false, true].
    • In other words, when subResult is [2], all possible permutations in the last loop have been output, and all used states have been cleared, without affecting the current recursion.
    • When the loop encounters a number that has already been used, it needs to skip over it to avoid repeated permutations.
  4. When the recursion terminates, the subResult is just a reference, meaning its value changes as the function runs, so it needs to be copied, otherwise the final output will be[]
/ * * *@param {number} n
 * @param {number} k
 * @return {number[][]}* /
var combine = function (n, k) {
  let result = []; // Store the result
  let subResult = []; // Store the result of each permutation
  let used = new Array(n + 1).fill(false); // The Boolean value corresponding to index indicates whether each value is used. Index indicates the value ranging from 1 to n

  // Generate all permutations recursively
  function dfs(current) {
    // 1. Recursive termination condition
    // When the length of the generated permutation equals the required length, the result is stored and the loop exits
    if (subResult.length === k) {
      // To save the current array to the result, you need to copy the original array, otherwise the subResult will be empty after the for loop ends
      result.push(subResult.slice());
      return;
    }

    // Use loops to generate different permutations
    // Assuming the first level of recursion, the subResult obtained by the for loop is [1], [2], [3], [4] respectively.
    // The recursion of the next layer continues on the basis of the first layer, while excluding the values prior to current to avoid repetition
    for (let i = current; i < used.length; i++) {
      // 2. The recursive logic of the current layer
      // If a value is already sorted, skip it to avoid double sorting
      if (used[i]) {
        continue;
      }
      // Indicate that the current value has been used and store the current value in a column
      used[i] = true;
      subResult.push(i);
      // 3. Drill down to the next level of recursion
      // Set the current index as the current of the next level to avoid repeated permutations
      dfs(i);
      // 4. Restore the current layer status
      // Deselect the current value
      used[i] = false; subResult.pop(); }}// If current is 1, filter out 0
  dfs(1);
  // Return the result
  return result;
};
Copy the code