题目

1.全排列 - 46

给定一个没有重复数字的序列，返回其所有可能的全排列。

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

思路：

要求：1、所有排列情况 2、没有重复元素
有出路、死路（包含重复元素的排列情况）
考虑回溯算法

解题步骤：

用递归模拟出所有的情况
遇到包含重复原素的情况就回溯（死路）
收集所有到达递归终点的情况，并返回

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
      // 定义返回的数组
    let res = []
    // 递归拿到所有的排列组合
    const rec = (path) => {
          // 递归终止条件：数组的长度达到了nums的长度
        if(path.length === nums.length) {
              // 就开始拼接返回数组
            res.push(path)
            return
        }
          // 遍历给出的数组
          // 1,2,3
          // 1,3,2
          // 2,1,3
          // 2,3,1
        nums.forEach(n => {
              // 如果已经包含，死路，就回溯
            if(path.includes(n)) return
              // 递归的拼接子数组
            rec(path.concat(n))
        })
    }
    rec([])
    return res
};

时间复杂度：O(n!), n! = 1x2x3…
空间复杂度：取决于递归的复杂度O(N)
2.子集 - 78
给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不相同

思路：

要求：1、所有的子集 2、没有重复的元素
有死路、出路
考虑使用回溯算法

解题步骤：

递归模拟出所有的情况
保证接的数字都是后面的数字
收集所有到达终点的情况，并返回

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
      // 定义返回数组
    const res = []
    // 定义递归，找出所有组合
    const rec = (path, l, start) => {
          // 递归终止条件，当path的长度为指定的长度时返回
        if(path.length === l) {
            res.push(path)
            return
        }
          // 从start遍历，保证concat的元素比原来的大
        for(let i = start; i< nums.length; i++) {
              // 递归的调用，并指定start为数组下一位，保证concat的元素比原来的大
            rec(path.concat(nums[i]), l, i + 1)
        }
    }
    // 循环调用n+1次，从长度为0开始一直到长度为nums的长度
    // 依次找出所有符合条件的子集
    for(let i = 0; i<= nums.length; i++) {
        rec([], i, 0)
    }
    return res
};

时间复杂度：O(2^N)，每个元素都有两种可能性（存在或者不存在）
空间复杂度：O(N)

算法思想 - 回溯算法

题目

1.全排列 - 46

2.子集 - 78