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] 10nums中的所有元素互不相同来源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 ListListInteger subsets(int[] nums) { ListListInteger result new ArrayList(); result.add(new ArrayList()); backTracking(nums.length, result, 0, nums, new ArrayList()); return result; } public void backTracking(int n, ListListInteger result, int index, int[] nums, ListInteger 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); } } }