注意:
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
数据范围:,集合中的任意元素满足
要求:空间复杂度 ,时间复杂度
import java.util.*; public class Solution { public void backtrack(int[] nums, int start, ArrayList<Integer> subset, ArrayList<ArrayList<Integer>> result) { result.add(new ArrayList<>(subset)); for (int i = start; i < nums.length; i++) { subset.add(nums[i]); backtrack(nums, i + 1, subset, result); subset.remove(subset.size() - 1); } } public ArrayList<ArrayList<Integer>> subsets(int[] nums) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); result.sort(Comparator.comparingInt((ArrayList<Integer> a) -> a.size()).thenComparingInt(a -> a.get(0))); return result; } }
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> subsets (int[] S) { // write code here Arrays.sort(S); recur(S ,new ArrayList<Integer>() ,0); return res; } public void recur(int[] arr ,ArrayList<Integer> list ,int index){ res.add(new ArrayList<Integer>(list)); for(int i=index;i<arr.length;i++){ list.add(arr[i]); recur(arr ,list ,i+1); list.remove(list.size()-1); } }
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { int n = S.length; ArrayList<ArrayList<Integer>>ans = new ArrayList<>(); ans.add(new ArrayList<Integer>()); for (int i = 0; i < n; i++) { int size = ans.size(); for (int j = 0; j < size; j++) { ArrayList<Integer>path = new ArrayList<Integer>(); path.addAll(ans.get(j)); path.add(S[i]); ans.add(path); } } int size=ans.size(); for (int i = 0; i <size - 1; i++) // Last i elements are already in place for (int j = 0; j < size - i - 1; j++) if (ans.get(j).size() > ans.get(j+1).size()){ ArrayList<Integer>tmp=new ArrayList<>(); tmp=ans.get(j); ans.set(j,ans.get(j+1)); ans.set(j+1,tmp); } return ans; } }
import java.util.*; //位运算求全子集 public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); if(S==null||S.length==0) return ans; //由于要子集当中的元素升序,所以可以先对S排序,最后子集当中求出的子集内部就是有序的。 Arrays.sort(S); int len = S.length; int num = (int)Math.pow(2,len); for(int i = 0;i<num;i++){ ArrayList<Integer> ls = new ArrayList<Integer>(); int count = 0; int flag = i; while(flag!=0){ int index = flag&1; if(index==1) ls.add(S[count]); flag = flag>>1; count++; } ans.add(ls); } return ans; } }
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if(S == null) return res; backtrack(res, S, 0, new ArrayList<>()); return res; } public void backtrack(ArrayList<ArrayList<Integer>> res, int[] S, int index, ArrayList<Integer> list){ res.add(new ArrayList<>(list)); for(int i = index; i < S.length; i++){ list.add(S[i]); backtrack(res, S, i + 1, list); list.remove(list.size() - 1); } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { Arrays.sort(S); int n=S.length; dfs(S,0,new ArrayList<Integer>()); return res; } public void dfs(int[]s,int index,ArrayList<Integer> temp){ res.add(new ArrayList<Integer>(temp)); for(int i=index;i<s.length;i++){ temp.add(s[i]); dfs(s,i+1,temp); temp.remove(temp.size()-1); } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); List<Integer> list = new LinkedList<>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { dfs(S,0); return ans; } void dfs(int[] nums, int index){ ans.add(new ArrayList(list)); for(int i = index; i< nums.length; i++){ list.add(nums[i]); dfs(nums,i+1); list.remove(list.size() - 1); } } }
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); if(S==null || S.length==0) return res; Arrays.sort(S); dfs(S,0,new ArrayList<Integer>(),res); return res; } private void dfs(int[] nums, int startIndex, ArrayList<Integer> subset, ArrayList<ArrayList<Integer>> res){ res.add(new ArrayList<Integer>(subset));//深复制 // res.add(subset); for(int i=startIndex;i<nums.length;i++){ subset.add(nums[i]); // ArrayList<Integer> newSet = new ArrayList<Integer>(subset); // newSet.add(nums[i]); // dfs(nums,i+1,newSet,res); dfs(nums,i+1,subset,res); subset.remove(subset.size()-1); } } }
ArrayList<ArrayList<Integer>> res; ArrayList<Integer> temp; public ArrayList<ArrayList<Integer>> subsets(int[] S) { res = new ArrayList<>(); int n=S.length; if(S==null || n==0){ res.add(new ArrayList<>()); return res; } temp = new ArrayList<>(); dfs(S,0); res.sort(new Comparator<ArrayList<Integer>>(){ @Override public int compare(ArrayList<Integer> l1,ArrayList<Integer> l2){ int num1 = l1.size()-l2.size(); if(num1==0){ int num2=0; for(int i=0;i<l1.size();i++){ if(l1.get(i)!=l2.get(i)){ num2 = l1.get(i)-l2.get(i); } } return num2; } else{ return num1; } } }); return res; } public void dfs(int[] S,int index){ if(index>S.length) return; if(index==S.length) {res.add(new ArrayList<>(temp));return;} temp.add(S[index]); dfs(S,index+1); temp.remove(temp.size()-1); dfs(S,index+1); }
import java.util.*; // 使用BFS实现所有子集有序 public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> ansLists = new ArrayList<>(); ansLists.add(new ArrayList<>()); if(S==null || S.length==0) return ansLists; Queue<List<Integer>> queue = new LinkedList<>(); for(int i=0; i<S.length; i++) { ArrayList<Integer> tmp = new ArrayList<>(); tmp.add(i); queue.add(tmp); } while(!queue.isEmpty()) { int size = queue.size(); for(int i=0; i<size; i++) { List<Integer> head = queue.poll(); ansLists.add(new ArrayList<>(head)); for(int j=head.get(head.size()-1)+1; j<S.length; j++) { head.add(j); queue.add(new ArrayList<>(head)); head.remove(head.size()-1); } } } for(List<Integer> list: ansLists) { for(int i=0; i<list.size(); i++) { list.set(i, S[list.get(i)]); } } return ansLists; } }
public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> lll = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); lll.add(list); huiSu(S,list,0, lll); return lll; } public void huiSu(int[] S, ArrayList<Integer> ll, int i, ArrayList<ArrayList<Integer>> lll){ for(; i < S.length; i++){ ArrayList<Integer> list = new ArrayList<>(ll); list.add(S[i]); lll.add(list); huiSu(S, list, i+1, lll); } }2. 位运算
public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> lll = new ArrayList<>(); int end = 1 << S.length; for (int i = 0; i < end; i++){ ArrayList<Integer> list = new ArrayList<>(); for(int j = 0; j< S.length; j++){ if((1<<j & i) !=0){ list.add(S[j]); } } lll.add(list); } return lll; }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> ls = new ArrayList(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { //保证了不会重复访问 int[] used = new int[S.length]; Arrays.sort(S); dfs(S,used,0); return res; } private void dfs(int[] a,int[] used,int start) { //这一步没有return; 保证了将每个遍历到的都输出一遍 res.add(new ArrayList(ls)); for(int i = start; i < a.length; i++) { if(used[i] == 1) continue; ls.add(a[i]); used[i] = 1; dfs(a,used,i); ls.remove(ls.size()-1); used[i] = 0; } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> ls = new ArrayList(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { int[] used = new int[S.length]; Arrays.sort(S); dfs(S,used,0); return res; } private void dfs(int[] a,int[] used,int start) { res.add(new ArrayList(ls)); for(int i = start; i < a.length; i++) { if(used[i] == 1) continue; ls.add(a[i]); used[i] = 1; dfs(a,used,i); ls.remove(ls.size()-1); used[i] = 0; } } }
import java.util.*; public class Solution { ArrayList<Integer> subResult = new ArrayList(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { // 升序排列 Arrays.sort(S); ArrayList<ArrayList<Integer>> result = new ArrayList(); ArrayList<Integer> subResult = new ArrayList(); // 一个都不选择 result.add(subResult); for(int i = 0 ; i< S.length; i++){ // 选择S[i]时,才会增加状态 原先的SubResult 每个增加一个S[i]; ArrayList<ArrayList<Integer>> newResult = new ArrayList(); for(ArrayList<Integer> lastSubResult : result){ ArrayList<Integer> newSubResult = new ArrayList(); newSubResult.addAll(lastSubResult); newSubResult.add(S[i]); newResult.add(newSubResult); } result.addAll(newResult); } return result; } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> arrays = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<Integer> array = new ArrayList<Integer>(); if (S.length == 0){ arrays.add(array); } Arrays.sort(S); function(S,0,S.length - 1,array); return arrays; } public void function(int[] arr,int start,int end,ArrayList<Integer> array){ if (!arrays.contains(new ArrayList<Integer>(array))){ arrays.add(new ArrayList<Integer>(array)); } if (start > end){ return ; } array.add(arr[start]); function(arr,start + 1,end,array); array.remove(array.size() -1); function(arr,start + 1,end,array); } }
利用位运算的性质,组合数共2^n个,用迭代,某位为1就代表取这个值,为0代表不取public ArrayList<ArrayList<Integer>> subsets(int[] S) { int size = 1 << S.length; ArrayList<ArrayList<Integer>> res = new ArrayList<>(size); for (int i = 0; i < size; i++) { res.add(process(i, S)); } return res; } private ArrayList<Integer> process(int index, int[] S){ ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < S.length; i++) { int bit = index >>> i; if((bit & 1) == 1) { list.add(S[i]); } } return list; }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); ArrayList<Integer>temp=new ArrayList<>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { Arrays.sort(S);//先排一下序 dfs(S,0); sort(res); return res; } public void dfs(int[]S, int index){ if(index==S.length){ res.add(new ArrayList<>(temp)); return; } dfs(S,index+1); temp.add(S[index]); dfs(S,index+1); temp.remove(temp.size()-1); } public void sort(ArrayList<ArrayList<Integer>> res){ Collections.sort(res, new Comparator<ArrayList<Integer>>(){//主要是排序最后的结果。。。。 public int compare(ArrayList<Integer> list1, ArrayList<Integer> list2){ if(list1.size() > list2.size()){ return 1; } else if(list1.size() < list2.size()){ return -1; } else{ return 0; } } }); } }
public ArrayList<ArrayList<Integer>> subsets(int[] S) { if (S==null||S.length==0) return new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); ArrayList<ArrayList<Integer>> res = new ArrayList<>(); Arrays.sort(S);//升序排序数组 dfs(0, S, list, res); //对结果集进行排序 每个list外部排序 内部一定是有序的 因为dfs搞好了已经 //list外部排序主要看长度 短的在前面 Collections.sort(res, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> list1, ArrayList<Integer> list2) { //我想要短的在前面 或者说 升序 那就是长度size 左-右 return list1.size()-list2.size(); } }); return res; } private void dfs(int level, int[] s, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> res) { if (level == s.length) { res.add(new ArrayList<>(list)); return; } //业务逻辑:子集问题就是一个分支:递归不选当前数直接下探 另一个分支:递归选当前数再下探 //分支1:如果选当前level为索引下的数 排序输出 没办法 必须先选 list.add(s[level]); dfs(level + 1, s, list, res); list.remove(list.size() - 1); //分支2:如果不选当前level为索引下的数 就直接从这里下探了 直到level大于len 逐层返回 dfs(level + 1, s, list, res); }