78. Subsets

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

题目给我们一个数组 nums，要求我们返回所有 nums 可能的子数组（不能重复）

解题思路

要求把元素中的子数组，我们一般使用回溯的框架加上不同条件判断处理

这一题最大的难点就是如何让子数组们不重复

要解决这一点，我们先来看看什么情况会重复，假设 nums 是 [1, 2, 3]

包含 1 的子数组有：[1], [1, 2], [1, 2, 3], [1, 3]

包含 2 的子数组有：[2], [2, 1], [2, 1, 3], [2, 3]

可以看到其中 [2, 1], [2, 1, 3] 重复了，因为它取到了下标比它小的数字 1

所以我们得到结论：在回溯时，我们只需要考虑取比当前下标大的元素即可

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
    const res = []

    const backtracking = (arr, start) => {
        res.push([...arr])

        for (; start < nums.length; start++) {
            arr.push(nums[start])
            backtracking(arr, start + 1)
            arr.pop()
        }
    }

    backtracking([], 0)
    return res
};