排列组合问题（不重复）–DFS实现

排列

从n个数中选取m个数进行排列，排列问题需要考虑取出数的顺序，比如取出元素3，5，因取出的顺序不同，故{3,5}和{5,3}是不同的排序序列

算法思想： 着眼于当前该怎么做，下一步的做法和当前做法一样 算法步骤：

首先定义一个数组visit，用来标记集合nums中的哪些数已经被取出，哪些数没有被取出（即避免重复取出同一个数），取出标记为1，还没有取出的标记为0，visit数组的元素默认全是0，即刚开始所有的数都没有被取出
取数的时候判断该数（假定是nums[i]）是否被取出，若没有被取出，则将当前元素存入一个数组res中，visit[i] = 1，取下一个数的时候直接DFS（i + 1）即可

如果取出的数的个数等于m的时候（即DFS的出口），返回，将最近标记为1的数重新标记为0并从res数组中移除，以便寻找下一个排列 代码实现：

var arrangement = function (nums, m) {
  let visit = Array(nums.length).fill(0)
  let res = [], arrs = [], idx = -1
  let DFS = function (cur) {
      if (res.length === m) {
          arrs[++idx] = []
          for (let i = 0; i < res.length; i++) {
              arrs[idx].push(res[i])
          }
          return
      }

      for (let i = 0; i < nums.length; i++) {
          if (!visit[i]) {
              visit[i] = 1
              res.push(nums[i])
              DFS(i + 1)
              visit[i] = 0
              res.pop()
          }
      }
  }
  DFS(0)
  return arrs
}

组合

与排列问题不同的是，组合不需要考虑取数的数的顺序，即{3,5}和{5,3}是同一种组合问题，即每次深搜的过程中应该从当前元素开始遍历，而不是从第一个元素开始遍历 代码实现：

var arrangement = function (nums, m) {
  let visit = Array(nums.length).fill(0)
  let res = [], arrs = [], idx = -1
  let DFS = function (cur) {
      if (res.length === m) {
          arrs[++idx] = []
          for (let i = 0; i < res.length; i++) {
              arrs[idx].push(res[i])
          }
          return
      }

      for (let i = cur; i < nums.length; i++) {
          if (!visit[i]) {
              visit[i] = 1
              res.push(nums[i])
              DFS(i + 1)
              visit[i] = 0
              res.pop()
          }
      }
  }
  DFS(0)
  return arrs
}

排列组合问题（dfs）

排列组合问题（不重复）–DFS实现

排列

组合

CATALOG