[LeetCode 78]Subsets

题目链接：subsets

import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Given a set of distinct integers, S, return all possible subsets.Note:Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets.For example,If S = [1,2,3], a solution is:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]] * */public class Subsets {//10 / 10 test cases passed.//Status: Accepted//Runtime: 218 ms//Submitted: 0 minutes ago//时间复杂度O(2^n) 空间复杂度 O(n)public List<List<Integer>> subsets = new ArrayList<List<Integer>>();public List<List<Integer>> subsets(int[] S) {Arrays.sort(S);subsets(S, 0, new ArrayList<Integer>());return subsets;}public void subsets(int[] S, int step, List<Integer> subset) {if(step == S.length) {subsets.add(subset);return;}//S[step] 不加入子集中subsets(S, step + 1, new ArrayList<Integer>(subset));//S[step] 加入子集中subset.add(S[step]);subsets(S, step + 1, new ArrayList<Integer>(subset));}//input{1 , 3, 2}// output//[]//[3]//[2]//[2, 3]//[1]//[1, 3]//[1, 2]//[1, 2, 3]public static void main(String[] args) {}}

，仿佛一支飘荡在水上的华丽咏叹调。