Skip to content

全排列问题解决

示例:   
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

javascript

const permute = function(nums) {
  const res = [];
  const cur = [];
  const len = nums.length;
  // 校验是否被使用
  const hash = {};
  function dfs(num) {
    if(num === len) {
      // copy
      res.push(cur.slice());
      return;
    }
    for(let i = 0; i < len; i++ ) {
      if(!hash[nums[i]]) {
        hash[nums[i]] = 1;
        cur.push(nums[i]);
        dfs(num+1);
        cur.pop();
        hash[nums[i]] = 0
      }
    }
  }

  dfs(0);

  console.log(res);
  return res;
}
permute([1,2,3])

组合问题:变化的“坑位”,不变的“套路”

示例: 输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

javascript

const subsets = function(nums) {
  const res = [];
  const cur = [];
  const len = nums.length;
  // 校验是否被使用
  function dfs(num) {
    res.push(cur.slice())
    for(let i = num; i < len; i++) {
      cur.push(nums[i]);
      dfs(i+1);
      cur.pop();
    }
  }
  dfs(0);
  console.log(res);
  return res;
}

subsets([1,2,3])

限定组合问题:及时回溯,即为“剪枝”

示例: 输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

javascript


/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
const combine = function(n, k) {
  const res = [];
  const cur = [];

  function dfs(num) {
    if(cur.length === k) {
      res.push(cur.slice());
      return;
    }

    for(let i = num; i < n; i ++) {
      cur.push(i);
      dfs(i+1);
      cur.pop();
    }
  }

  dfs(1);
  return res;
}

combine(4,2)