注意:
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
数据范围:,集合中的任意元素满足
要求:空间复杂度 ,时间复杂度
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(),S.end()); for(int i = 0; i <= S.size(); ++ i) dfs(S,0,i);//因为标准输出是按size()大小顺序来的,所以要把size作为dfs的形参 return result; } void dfs(vector<int> S, int start, int k){ if(k<0) return; else if(k==0) result.push_back(tmp); else{ for(int i = start; i < S.size(); ++ i){ tmp.push_back(S[i]); dfs(S,i+1,k-1); tmp.pop_back(); } } } private: vector<vector<int> > result; vector<int> tmp; };
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > res; res.push_back(vector<int>()); sort(S.begin(), S.end()); for (int i = 1; i < S.size() + 1; i++) { // 当前集合大小 pick(S, vector<int>(), 0, res, i); } return res; } void pick(vector<int> &S, vector<int> vec, int start, vector<vector<int> > &res, int k) { if (vec.size() == k) { // 如果到达目标大小,则添加 res.push_back(vec); return; } for (int i = start; i < S.size(); i++) { vec.push_back(S[i]); pick(S, vec, i + 1, res, k); vec.pop_back(); } } };
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); Arrays.sort(S); LinkedList<Integer> list=new LinkedList<>(); dfs(res,list,0,S); return res; } public void dfs(ArrayList<ArrayList<Integer>> res,LinkedList<Integer> list, int k, int[] S){ res.add(new ArrayList<>(list)); for(int i=k;i<S.length;i++){ list.add(S[i]); dfs(res,list,i+1,S); list.removeLast(); } } }
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); } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); //用回溯法找出所有子集然后按子集大小排序 public ArrayList<ArrayList<Integer>> subsets(int[] S) { if(S==null||S.length<0) return res; ArrayList<Integer> list=new ArrayList<>(); Arrays.sort(S); Findsubset(S,0,list); 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; } } }); return res; } public void Findsubset(int[] S,int start,ArrayList<Integer> list){ res.add(new ArrayList<Integer>(list)); for(int i=start;i<S.length;i++){ list.add(S[i]); Findsubset(S,i+1,list); list.remove(list.size()-1); } } }
// 用了两个sort class Solution { public: void dfs(int step, vector<int> &S, vector<int> &vec, vector<vector<int> > &res) { for(int i=step;i<S.size();++i) { vec.push_back(S[i]); res.push_back(vec); dfs(i+1, S, vec, res); vec.pop_back(); } } vector<vector<int> > subsets(vector<int> &S) { int len = S.size(); vector<vector<int> > res; vector<int> vec; res.push_back(vec); if(!len) return res; sort(S.begin(), S.end()); dfs(0, S, vec, res); sort(res.begin(), res.end(), [](const vector<int> &a, const vector<int> &b) -> bool { return a.size()==b.size()?a<b:a.size()<b.size(); }); return res; } };
C++ DFS+自定义比较函数
class Solution {
public:
void mysort(vector<vector<int>>&res){
int n = res.size();
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (res[i].size() > res[j].size()){
vector<int >temp = res[i];
res[i] = res[j];
res[j] = temp;
}
if (res[i].size() == res[j].size()){
for (int k = 0; k < res[i].size(); k++){
if (res[i][k]>res[j][k]){
vector<int >temp = res[i];
res[i] = res[j];
res[j] = temp;
break;
}
if(res[i][k]<res[j][k])
break;
}
}
}
}
}
void dfs(vector<vector<int>>&res, vector<int>temp, vector<int>&s, int deep){
if (deep == s.size())
return;
for (int i = deep; i < s.size(); i++){
temp.push_back(s[i]);
res.push_back(temp);
dfs(res, temp, s, i + 1);
temp.pop_back();
}
}
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int>>res;
vector<int>temp;
res.push_back(temp);
dfs(res, temp, S, 0);
mysort(res);
return res;
}
};
// 这题主要是排序恶心。。。 import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); ArrayList<Integer> inner = new ArrayList<>(); result.add(inner); int SLen = S.length; int index = 0; while (index != SLen) { ArrayList<ArrayList<Integer>> temp = new ArrayList<>(); for (ArrayList innerList : result) { ArrayList<Integer> tempInnerlist = new ArrayList<>(innerList); tempInnerlist.add(S[index]); // 内部排序 Collections.sort(tempInnerlist); temp.add(tempInnerlist); } result.addAll(temp); index++; } // 外面排个序 Collections.sort(result, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { int o1Size = o1.size(); int o2Size = o2.size(); if (o1Size != o2Size) return Integer.compare(o1Size, o2Size); else { for (int i = 0; i < o1.size(); i++) { int comp = Integer.compare(o1.get(i), o2.get(i)); if (comp != 0) return comp; } } return 0; } }); return result; } }
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; }
// #################### function declaration #################### void backtracking(int* A, const int ALen, int position, int* cur, int* curSize, int** ans, int* ansSize, int** ansColumsSizes); // 其中x表示底数,y表示幂值 long int power(int x, int y); // #################### function declaration #################### /** * * @param A int整型一维数组 * @param ALen int A数组长度 * @return int整型二维数组 * @return int* returnSize 返回数组行数 * @return int** returnColumnSizes 返回数组列数 */ int** subsets(int* A, int ALen, int* returnSize, int** returnColumnSizes) { const int n = power(2, ALen); int** ans = (int**) malloc(n * sizeof(int*)); *returnSize = 0; *returnColumnSizes = (int*) malloc(n * sizeof(int)); int cur[ALen], curSize = 0; backtracking(A, ALen, 0, cur, &curSize, ans, returnSize, returnColumnSizes); return ans; } void backtracking(int* A, const int ALen, int postiton, int* cur, int* curSize, int** ans, int* ansSize, int** ansColumsSizes) { *(ans + *ansSize) = (int*) malloc(*curSize * sizeof(int)); memcpy(*(ans + *ansSize), cur, *curSize * sizeof(int)); (*ansColumsSizes)[(*ansSize)++] = *curSize; int i; for (i = postiton; i < ALen; ++i) { *(cur + (*curSize)++) = *(A + i); backtracking(A, ALen, i + 1, cur, curSize, ans, ansSize, ansColumsSizes); --(*curSize); } } // 数学上的递推式为: x^y == x^(y - 1) * x long int power(int x, int y) { // recursion exit condition (x^0 次方等于1) if (!y) return 1; return power(x, y - 1) * x; }
ArrayList<ArrayList<Integer>> result=new ArrayList<>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { Arrays.sort(S); LinkedList<Integer> track = new LinkedList<>(); DFS(S,track); return result; } public void DFS(int[] S, LinkedList<Integer> res){ result.add(new ArrayList<>(res)); for (int i = 0; i < S.length; i++) { if(res.contains(S[i])) continue; if (res.size()!=0&&res.getLast()>S[i]) continue; res.add(S[i]); DFS(S,res); res.removeLast(); } }
class Solution { public: static int cmp(vector<int>a,vector<int>b) { if(a.size()==b.size()) return a<b; else return a.size()<b.size(); } vector<vector<int> > subsets(vector<int> &S) { int sz=S.size(); std::vector<std::vector<int>> ans; for(int i=0;i<(1<<sz);i++) { std::vector<int>tmp; for(int j=0;j<sz;j++) { if(i&(1<<j)) { tmp.emplace_back(S[j]); } } sort(tmp.begin(),tmp.end()); ans.emplace_back(tmp); } sort(ans.begin(),ans.end(),cmp); return ans; } };
/* 回溯法。 必须包含空子集。 加入列表时,必须新建一个列表对象,不然回溯删除时会导致答案中的元素被删除。 导致最后返回空列表。 */ import java.util.*; public class Solution { private ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); private int[] arr; private int len; public ArrayList<ArrayList<Integer>> subsets(int[] S) { this.arr = S; len = arr.length; Arrays.sort(arr); for (int i = 0; i <= len; i++) { ArrayList<Integer> list = new ArrayList<>(); backtracking(i, 0, list); } return ans; } public void backtracking(int k, int start, ArrayList<Integer> list) { if (k < 0) return; if (k == 0) { ans.add(new ArrayList(list)); return; } else { for (int i = start; i < len; i++) { list.add(arr[i]); backtracking(k - 1, i + 1, list); list.remove(list.size() - 1); } } } }
//AC版本 class Solution { public: void dfs(vector<vector<int> >&res,vector<int>ans,int val,int size,vector<int> &S) { if(val>=size) return ; for(int i=val;i<size;++i) { ans.push_back(S[i]); res.push_back(ans); dfs(res,ans,i+1,size,S); ans.pop_back(); } return ; } vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> >res; sort(S.begin(),S.end()); res.push_back({}); vector<int>ans; dfs(res,ans,0,S.size(),S); for(int i=0;i<res.size()-1;++i) for(int j=0;j<res.size()-i;++j) if(res[j].size()>res[j+1].size()) swap(res[j],res[j+1]); return res; } };
//顺序不对,不过也不失一种好办法class Solution { public: vector<int> GetSub(int x,vector<int>&S) { vector<int>temp; for(int i=1;i<=static_cast<int>(S.size());++i) { if(x&1) temp.push_back(S[i-1]); x=x>>1; } return temp; } vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> >res; sort(S.begin(),S.end(),less<int>()); int MaxSize=1<<S.size(); for(int i=0;i<MaxSize;++i) res.push_back(GetSub(i,S)); return res; } };
//本题的整体思路还是找子集问题,问题再与最后输出顺序和答案不一致,可以通过以下方法解决 //1、首先通过经典非递归方法获得所有子集集合v。2、通过sort对v进行排序(按vector中首元素大小排序) //3、循环遍历v按照子元素集合的个数添加到result中,即为最终结果。 class Solution { public: vector<vector<int> > subsets(vector<int> &S) { int len = S.size(); vector<vector<int>> v; vector<int> vBlank; v.push_back(vBlank); if(len == 0) return v; sort(S.begin(),S.end()); int n; for(int i=0;i<len;i++) { n = v.size(); for(int j=0;j<n;j++) { vector<int> vTmp = v[j]; vTmp.push_back(S[i]); v.push_back(vTmp); } } sort(v.begin(),v.end()); vector<vector<int>> result; result.push_back(vBlank); for(int i=1;i<=len;i++) { for(int j=0;j<v.size();j++) if(v[j].size()==i) result.push_back(v[j]); } return result; } };
import java.util.*; public class Solution { public static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); public static boolean[] v = new boolean[100]; public static void recursive(int num,int[] nums){ if(num >= nums.length){ ArrayList<Integer> l = new ArrayList<>(); for(int i = 0 ; i < nums.length ; i++){ if(v[i]){ l.add(nums[i]); } } list.add(l); return ; } v[num] = true; recursive(num + 1, nums); v[num] = false; recursive(num + 1, nums); } public ArrayList<ArrayList<Integer>> subsets(int[] S) { list.clear(); Arrays.sort(S); recursive(0,S); Collections.sort(list, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { if (o1.size()!=o2.size()) { return o1.size()-o2.size(); }else { for (int i = 0; i < o1.size(); i++) { int comp=o1.get(i)-o2.get(i); if (comp!=0) return comp; } } return 0; } }); return list; } }