题目链接:
1. 题目介绍(Subsets)
Given an integer array nums of unique elements, return all possible subsets (the power set).
【Translate】: 给定一个包含多个唯一元素的整数数组,返回所有可能的子集(幂集)。
The solution set must not contain duplicate subsets. Return the solution in any order.
【Translate】: 解决方案集不得包含重复的子集。你可以以任何顺序返回解决方案。
【测试用例】:
【条件约束】:
2. 题解
2.1 双循环
原题解来自于TWiStErRob的Simple iteration (no recursion, no twiddling) + explanation。
他的想法是从一个空子集开始,然后取或不取输入数组中的下一个元素,他通过了listMap的size()巧妙的设置了内层循环的范围,保证了所有情况。下方是输入[1,2,3]的情况:
由于该题对于返回结果的order没有要求,所有这里我省略了原题解中的sort()排序,如果要求了排序,这就需要到了sort()。
class Solution {public List<List<Integer>> subsets(int[] nums) {int n = nums.length;List<List<Integer>> listMap = new ArrayList<>();listMap.add(new ArrayList<>());for (int i = 0; i < n; i++){for (int j = 0,size = listMap.size(); j < size; j++){List<Integer> list = new ArrayList<>(listMap.get(j));list.add(nums[i]);listMap.add(list);}}return listMap;}
}
2.2 递归
原题解来自于yetiiiiii的 📌 [Java] Intuition of Approach | Backtracking。
class Solution {List<List<Integer>> result;public List<List<Integer>> subsets(int[] nums) {result = new ArrayList();if(nums==null || nums.length==0) return result;subsets(nums,new ArrayList<Integer>(), 0);return result;}private void subsets(int[] nums, ArrayList<Integer> temp, int index) {// base conditionif(index >= nums.length) {result.add(new ArrayList<>(temp));return;}// main logic// case 1 : we pick the elementtemp.add(nums[index]);subsets(nums, temp, index+1); // move aheadtemp.remove(temp.size()-1);// case 2 : we don't pick the element ( notice, we did not add the current element in our temporary listsubsets(nums, temp, index+1); // move ahead}
}
更多的题解详见 issac3的 A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)。
3. 参考资料
[1] List<List<Integer>>初始化方法 | CSDN
[2] power set的定义和理解 | CSDN