description: Given a set of distinct integers, return all possible subsets.
Notice
Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. Have you met this question in a real interview? Yes Example If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
解题思路:虽然这道题目做了少说也有5次了,但是每次做都有新发现。 recursion不是这么容易理解。 首先进行边界检查,判断是否有越界的结果。 对数组进行排序。 创建一个新的util函数,该函数通过位置对数组的数字进行排序选择,recursion的方式,切记有一个进入和删除的过程。
class Solution { /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsets(int[] nums) { // write your code here ArrayList<ArrayList<Integer>> result = new ArrayList<>(); ArrayList<Integer> set = new ArrayList<>(); if (nums == null || nums.length == 0) { return result; } Arrays.sort(nums); util(result, 0, nums, set); return result; } private void util(ArrayList<ArrayList<Integer>> result, int position, int[] nums, ArrayList<Integer> set) { result.add(new ArrayList<Integer>(set)); for (int i = position; i < nums.length; i++) { set.add(nums[i]); util(result, i + 1, nums, set); set.remove(set.size() - 1); } } }