LeetCode 精选 TOP 面试题（Java 实现）—— 子集

一、题目描述

1.1 题目

• 子集

• 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

• 说明：解集不能包含重复的子集。

• 示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

1.2 知识点

• 回溯算法
• 位运算

1.3 题目链接

• https://leetcode-cn.com/problems/subsets/

二、解题思路

2.1 自研思路

  使用递归回溯算法思想，层层递进再回溯，将每一层得到的结果都保存至结果数组中即可。

2.2 示例思路

  可以直接从前或从后遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集。

三、实现代码

3.1 自研实现

class Solution {

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

    private void backtrack(int[] nums, int index, ArrayList list){

        res.add(new ArrayList<Integer>(list));
        for(int i = index; i < nums.length; i++){
            list.add(nums[i]);
            backtrack(nums, i+1, list);
            list.remove(list.size()-1);
        }
    }
}

3.2 示例代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
           int all = res.size();
            for (int j = 0; j < all; j++) {
                List<Integer> tmp = new ArrayList<>(res.get(j));
                tmp.add(nums[i]);
                res.add(tmp);
            }
        }
        return res;
    }
}