Given a set of distinct integers, S, return all possible subsets.
Note:
For example,
If S = [1,2,3]
, a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); if (S == null || S.length == 0) return list; Arrays.sort(S); HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>(); recursion(set, new ArrayList<Integer>(), S, 0); return new ArrayList<ArrayList<Integer>>(set);//wrong here!! } private void recursion(HashSet<ArrayList<Integer>> set,ArrayList<Integer> list, int[] s, int level) { if (set.contains(list)) { return; } else { set.add(list); for(int i = level ; i < s.length ; i++){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(list); temp.add(s[i]); recursion(set, temp, s, i+1);//此处不应是level +1 ,而是迭代的参数加1. Wrong here. 可以理解为level是大循环,里面是小循环 } } } }
mistake: hashset没想到用,没有重复的情况直接使用hashset. recursion题目就是两段式填空,main 和recursion
lsit 局部变量避免线程安全问题 if 作为成员变量,有线程安全问题,但很简洁