题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

题目分析

本质是组合，是无序的，而排列是有序的。
例如 [1, 2] 和 [2, 1]，视为同一个结果。
如果直接按照排列的 DFS 来做，会产生很多顺序不同的结果，需要额外的成本做去重。
可以通过在 DFS 中引入一个 index 来解决重复问题，要求下一个结点的位置在 index 之后，也就是不许向当前的左侧搜索，只能向右侧搜索。
这样就不会产生重复的搜索，效率最高。

Java

private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> list = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
    dfs(nums, -1);
    return ans;
}

private void dfs(int[] nums, int index) {
    ans.add(new ArrayList<>(list));
    for (int i = index + 1; i < nums.length; i++) {
        Integer x = nums[i];
        list.add(x);
        dfs(nums, i);
        list.remove(x);
    }
}

Kotlin

private val ans = ArrayList<List<Int>>()
private val list = ArrayList<Int>()

fun subsets(nums: IntArray): List<List<Int>> {
    dfs(nums, -1)
    return ans
}

private fun dfs(nums: IntArray, index: Int) {
    ans.add(ArrayList(list))
    if (index == nums.size - 1) {
        return
    }
    for (i in index + 1 until nums.size) {
        val x = nums[i]
        list.add(x)
        dfs(nums, i)
        list.remove(x)
    }
}