题目

78. 子集

题解

代码

import java.util.*;

public class code78 {

    public static List<List<Integer>> subsets(int[] nums) {
        // Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        dfs(res, list, 0, nums);
        return res;
    }

    public static void dfs(List<List<Integer>> res, List<Integer> list, int start, int nums[]) {
        res.add(new ArrayList<>(list));

        for (int i = start; i <= nums.length - 1; i++) {
            list.add(nums[i]);
            dfs(res, list, i + 1, nums);
            list.remove(list.size() - 1);
        }
    }

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

参考

  1. 回溯算法——题解一
  2. 二进制位，逐个枚举，DFS 三种思路，9+ 种以上的写法——题解二
  3. 位运算——题解三
  4. 详细通俗的思路分析，多解法——题解四
  5. 回溯 + 位掩码（Python 代码、Java 代码）