JAVA练习329- 子集

题目概览

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

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

示例 2：

输入：nums = [0]输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums中的所有元素互不相同

来源：78. 子集 - 力扣（LeetCode）

解题分析

方法：回溯

我们可以用一个集合 prefix 来存储前缀，令当前索引为 i，每一次递归我们可以遍历 [ i, n - 1 ] 的元素，此时 prefix 就为 [0, i-1]，每次遍历我们将该元素加入 prefix，此时 prefix 就是一个子集，然后递归遍历 i + 1 的集合，递归遍历完成后，回溯 prefix，将下一个元素加入 prefix，继续重复操作，直到所有元素遍历完成，此时的过程中所有的 prefix 就是子集。

时间复杂度：O(nxn!)
空间复杂度：O(n)

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); backTracking(nums.length, result, 0, nums, new ArrayList<>()); return result; } public void backTracking(int n, List<List<Integer>> result, int index, int[] nums, List<Integer> prefix) { if (index == n) { return; } for (int i = index; i < n; ++i) { prefix.add(nums[i]); backTracking(n, result, i + 1, nums, prefix); result.add(new ArrayList<>(prefix)); prefix.remove(prefix.size() - 1); } } }