【LeetCode】78. 子集（Java）

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

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

这道题做完后，可以再做做90. 子集 II。

解法一

迭代

class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); //放入一个空集合 result.add(new ArrayList<>()); //遍历所有数字 for (int num : nums) { //遍历所有小集合 int size = result.size(); for (int i = 0; i < size; i++) { //在小集合原先的基础上，再加上当前值，然后保存到大集合里 List<Integer> list = new ArrayList<>(result.get(i)); list.add(num); result.add(list); } } // 添加前的大集合 多添加的小集合 添加后的大集合 //第一轮： [] -> [1] -> [],[1] //第二轮： [], [1] -> [2], [1,2] -> [],[1],[2],[1,2] //.... return result; } }

解法二

回溯

class Solution { public List<List<Integer>> subsets(int[] nums) { //回溯 List<List<Integer>> res = new ArrayList<>(); backtrack(nums, 0, res, new ArrayList<>()); return res; } //回溯 private void backtrack(int[] nums, int start, List<List<Integer>> res, List<Integer> cur) { //把递归过来的cur添加到res中 //这一步添加并不是添加当前这个方法，而是添加上一个方法递归传递过来的cur res.add(new ArrayList<>(cur)); //如果start == num.length，那么下面这个循环不会执行，只执行上面的添加操作 //即，当start == num.length时为出口 for (int i = start; i < nums.length; i++) { //递归的第一个方法，当前cur为空集合，添加一个（上一轮为空，本轮集合内的个数为1） cur.add(nums[i]); //那么，第二个方法为2个数（下一轮轮集合内的个数为2） backtrack(nums, i + 1, res, cur); //要移除添加的值（保证本轮的集合内个数为1，即要保证下次循环添加后集合内的个数也是为1） cur.remove(cur.size() - 1); } } }

解法二和解法三，是看题解区数据结构和算法写的题解，加的注释如果看不懂就请忽略吧，本人也是个菜鸟，只能根据自己的理解写注释，看不懂的话，DeBug一步一步走，慢慢熟悉。

解法三

DFS（深度优先搜索）

class Solution { public List<List<Integer>> subsets(int[] nums) { //DFS（深度优先搜索） List<List<Integer>> res = new ArrayList<>(); //因为DFS是一个一个去遍历，所以不会有空的集合，需要自己添加 res.add(new ArrayList<>()); preOrder(nums, 0, res, new ArrayList<>()); return res; } //DFS（深度优先搜索） public static void preOrder(int[] nums, int i, List<List<Integer>> res, ArrayList<Integer> subset) { if (i >= nums.length) return; // 到了新的状态，记录新的路径，要重新拷贝一份 subset = new ArrayList<Integer>(subset); // 这里因为是内存传递，所以保存到res的subset会因为下面的subset的修改而修改 // 1. 前序遍历，先添加，然后修改 res.add(subset); //递归 preOrder(nums, i + 1, res, subset); subset.add(nums[i]); // 2. 把添加操作放这里也是可以的，这是中序遍历 // res.add(subset); //递归 preOrder(nums, i + 1, res, subset); // 3. 后序遍历 // res.add(subset); } }

不熟悉的回溯和DFS的话，需要多做些类似的题目，找找感觉。本人目前也在找感觉中o(╥﹏╥)o。。。