集合的所有子集(一)_

箫声

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;
};

发表于 2018-02-19 21:14:16 回复(1)

ExtraLocker

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();
        }
    }
};

发表于 2020-04-14 21:21:24 回复(1)

tofine

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();
        }
    }
}

发表于 2020-08-12 22:36:27 回复(0)

Java

啊哈哈h

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);
        }

    }
}

发表于 2021-11-09 10:16:21 回复(0)

Python

小狗最6

class Solution:
def subsets(self , A ):
# write code here
res = []
state = []
def back(state,num = 0):
if state in res:
return
else:
res.append(state)
for i in range(num,len(A)):
back(state + [A[i]],i+1)
A.sort()
back(state,0)
return res

发表于 2020-08-30 18:19:19 回复(0)

Java

HW柯可

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);
            } 
    }
}

发表于 2020-04-21 00:20:23 回复(0)

继续加油～

// 用了两个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;
    }
};

编辑于 2019-05-05 10:03:41 回复(0)

顾翅

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;
}
};

发表于 2018-06-07 21:59:52 回复(1)

Java

WangC1117

两种方法 1. 回溯

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;
    }

发表于 2021-08-05 16:39:27 回复(3)

勇敢牛牛，不怕困难！

// #################### 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;
}

发表于 2021-07-09 09:13:32 回复(0)

Python

LHC0512

Python

import itertools

class Solution:
    def subsets(self, A):
        res = []
        res.append([])
        for i in range(1, len(A) + 1):
            s = itertools.combinations(A, i)
            for v in s:
                res.append(list(v))
        return res

发表于 2021-02-23 21:28:01 回复(0)

Java

so_what_xxxx

//无栈才是快的 BFS典型应用

public class Solution {

private ArrayList<ArrayList<Integer>> res=null;
private ArrayList<Integer> temp=null;
    private int[] num=null;
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
         this.res=new ArrayList<>();
      this.temp=new ArrayList<>();
      Arrays.sort(S);
      this.num=S;
      res.add(new ArrayList<>(temp));
      LinkedList<ArrayList<Integer>> queue1=new LinkedList<>();
      LinkedList<Integer> queue2=new LinkedList<>();
      queue1.addLast(temp);
      queue2.addLast(0);
      while(!queue1.isEmpty()) {
           this.temp=queue1.removeFirst();
           int start=queue2.removeFirst();
           for(int i=start;i<num.length;i++) {
      temp.add(num[i]);
      ArrayList<Integer> ele=new ArrayList<>(temp);
      res.add(ele);
      queue1.addLast(ele);
      queue2.addLast(i+1);
      temp.remove(temp.size()-1);
      }
      }
      return res;
}
}

发表于 2021-02-20 23:23:37 回复(0)

Z宇锤锤

  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();
        }
    }

发表于 2020-12-04 16:32:21 回复(0)

loo2fix

直接二进制枚举子集就好了。

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;
    }
};

发表于 2019-12-16 00:51:14 回复(0)

tuweilong

/*
回溯法。
必须包含空子集。
加入列表时，必须新建一个列表对象，不然回溯删除时会导致答案中的元素被删除。
导致最后返回空列表。
*/
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);
            }
        }
    }
}

发表于 2019-06-21 10:56:29 回复(0)

C/C++

但求八月九月好运！

//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;
    }
};

编辑于 2019-06-14 21:09:30 回复(0)

C/C++

J.Fan

//本题的整体思路还是找子集问题，问题再与最后输出顺序和答案不一致，可以通过以下方法解决
//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;
    }
};

发表于 2019-01-13 18:35:12 回复(1)

Howie59

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;
    }
}

发表于 2018-10-24 19:56:12 回复(0)

秒速__五厘米

还是带回溯的dfs

发表于 2018-01-15 17:01:56 回复(0)

曾~

/*  用dfs
*   因为是要求非递减子序列集合，所以先对数组按增序排序
*   然后用深度优先搜索
**/

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        ArrayList<Integer> list=new ArrayList<>();
        if(S.length==0){
            return res;
        }
        Arrays.sort(S);
        dfs(res,list,S,0);
        return res;
    }
    public void dfs(ArrayList<ArrayList<Integer>> res,ArrayList<Integer> list,int[] num,int start){
        res.add(new ArrayList<Integer>(list));
        for(int i=start;i<num.length;++i){
            list.add(num[i]);
            dfs(res,list,num,i+1);
            list.remove(list.size()-1);
        }
    }
}

发表于 2017-05-05 17:50:58 回复(3)

集合的所有子集(一)

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题