【Leetcode-78】Subsets（子集）

Github：Leetcode-78. Subsets(代码实现)

Leetcode-78. Subsets

Leetcode-78. 子集

在不重复元素数组中，寻找所有可能的非重复子集。

1、注意一个特殊的集合空集，空集是任何集合的子集；

2、回溯算法（试探法）

• 在搜索尝试过程中寻找问题的解，在这个问题中就是尝试寻找合适的子集；
• 如果不满足条件，此路不通，就回退一步重新选择，如果不满足非重复子集的条件，回退到上一步，走别的路径寻找；

package com.jpeony.leetcode.n0078;

import java.util.ArrayList;
import java.util.List;


public class N78_Subsets {

    
    private static List> subsets(int[] nums) {
        List> ans = new ArrayList<>();
        backtrack(0, nums, ans, new ArrayList());
        return ans;
    }

    private static void backtrack(int i, int[] nums, List> ans, ArrayList temp) {
        // 每个子集放入返回结果
        ans.add(new ArrayList<>(temp));
        System.out.println("i = " + i + ", ans = " + ans + ", cur = " + temp);
        // 寻找符合条件的子集合
        for (int j = i; j < nums.length; j++) {
            temp.add(nums[j]);
            backtrack(j + 1, nums, ans, temp);
            System.out.println("backtrack-before = " + ans);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List> subsets = subsets(nums);
        System.out.println("subsets = " + subsets);
    }
}

时间复杂度：O(n×2^n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。

空间复杂度：O(n)。渐进空间为存储子集的临时列表，n 为子集个数，所以空间复杂度为 O(n)。