C/C++

zxjcarrot

首先按升序排序再利用二进制位来表示子集按((2^n) - 1)到 1 的顺序生成子集, 生成子集时候按(n-1)到0的顺序.

class Subset {
public:
    vector<vector<int> > getSubsets(vector<int> A, int n) {
        // write code here
        sort(A.begin(), A.end());
        int size = 1 << n;
        vector<vector<int> >subsets;
        for (int i = size - 1; i > 0; --i) {
            vector<int> subset;
            for (int j = n - 1; j >= 0; --j) {
                if ((i >> j) & 1) {
                    subset.push_back(A[j]);
                }
            }
            subsets.push_back(subset);
        }
        return subsets;
    }
};

编辑于 2017-01-22 15:11:57 回复(17)

nailperry

首先说明一点：

测试用例有误，输出顺序应为[[3, 2, 1], [3, 2], [3, 1], [3], [2, 1], [2], [1]]的顺序。

解题思路：

在n-1个数的所有子集的基础上生成n个数的所有子集，sets(n)通过如下步骤获得：

1. 在sets(n-1)的所有子集前边插入当前元素A[n-1]。

2. A[n-1]单独作为一个子集[A[n-1]]。

3. sets(n-1)同时也应包含到sets(n)中。

举个例子：

A={1,2,3};

1.首先生成一个元素的子集sets(1)={{1}}。

2.加入元素2，则sets(2)由三部分组成：

（1）在sets(1)的所有子集前边插入当前元素A[1]=2，得到{{2,1}}；

（2）A[1]单独作为一个子集{2}；

（3）sets(1)同时也应包含到sets(2)中，sets(3) = {{2,1},{2},{1}}。

3.加入元素3，则sets(3)由三部分组成：

（1）在sets(2)的所有子集前边插入当前元素A[2]=3，得到 {{3,2,1},{3,2},{3,1}}；

（2）A[2]单独作为一个子集{3}；

（3）sets(2)同时也应包含到sets(3)中，sets(3) = {{3,2,1},{3,2},{3,1},{3},{2,1},{2},{1}}。

	public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        if(A==null||A.length==0)
        	return new ArrayList<>();
        Arrays.sort(A);// 数组A从小到大排序        
        return getSubsetsCore(A,n);
    }
	public ArrayList<ArrayList<Integer>> getSubsetsCore(int[] A,int n){
		ArrayList<ArrayList<Integer>> outter = new ArrayList<ArrayList<Integer>>();	
		ArrayList<Integer> inner;
		if(n==1){// 循环终止条件
			inner = new ArrayList<Integer>();
			inner.add(A[0]);
			outter.add(inner);
			return outter;	
		}
		ArrayList<ArrayList<Integer>> tmp = getSubsetsCore(A, n-1);
		int i,j;
		for (i = 0; i < tmp.size(); i++) {// 1. 在sets(n-1)的所有子集前边插入当前元素A[n-1]。
			inner = new ArrayList<Integer>();
			inner.add(A[n-1]);
			for (j = 0; j < tmp.get(i).size(); j++) {
				inner.add(tmp.get(i).get(j));
			}
			outter.add(inner);			
		}
		inner = new ArrayList<Integer>();
		inner.add(A[n-1]);
		outter.add(inner);// 2. A[n-1]单独作为一个子集[A[n-1]]。
		outter.addAll(tmp);// 3. sets(n-1)同时也应包含到sets(n)中。
		return outter;		
	}

编辑于 2015-09-09 19:56:14 回复(6)

Python

Yannyezixin

思路：

初始结果集为 [ [A[0] ]

遍历剩余 A[1] ~ A[n - 1]. 每取出一个元素遍加到结果集：

复制一份结果集，并把元素加入到结果集中的每个集合的头部
合并复制的结果集 + 只有当前元素的集合 + 原始结果集

# -*- coding:utf-8 -*-
class Subset:
    # 返回二维[[],[],[]]
    def getSubsets(self, A, n):
        result = [[A[0]]]
        for i in range(1, n):
            tmp = result[:]
            for j in range(len(tmp)):
                tmp[j] = [A[i]] + tmp[j]
            result = tmp + [[A[i]]] + result
        return result

发表于 2016-08-05 10:17:04 回复(1)

Aurora1

    //总共有2^n-1种情况（n是数组个数），每种情况代表一个数，一个数的各位代表取或者不取。
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(A);
        int max = 1 << n;
        for (int k = max - 1; k >= 1; k--) {
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for (int i = k, index = 0; i > 0; i >>= 1, index++) {
                if ((i & 1) == 1) {
                    arr.add(0, A[index]);
                }
            }
            list.add(arr);
        }
        return list;
    }

编辑于 2016-08-28 21:27:34 回复(3)

Tothink

样例坑爹, 应该是这样
[[3, 2, 1], [3, 2], [3, 1], [3], [2, 1], [2], [1]]

发表于 2015-08-26 17:03:16 回复(1)

向宇家女婿

#if 1
bool Larger(int a, int b)
{
	return a > b;
}
vector<vector<int> > getSubsets(vector<int> A, int n) 
{
	vector<vector<int> > allVec;
	if (A.size() == 0)
		return allVec;

	sort(A.begin(), A.end(), Larger);
	for (int i = 0; i < A.size(); i++)
	{
		vector<vector<int> > newV = allVec;
		allVec.clear();
		for (auto v : newV)
		{
			auto vcopy = v;
			v.push_back(A[i]);
			allVec.push_back(v);
			allVec.push_back(vcopy);
		}
		vector<int> newv;	// 加入null+A[i]单元素的vector
		newv.push_back(A[i]);
		allVec.push_back(newv);
	}
	return allVec;
}
#endif

对原数据从大到小排序后，从元素开始，取or不取，两种情况，形成vector压入，往后遍历元素，取出之前所有的vector，再之后push入元素或者不push，再把新的vector压回，新增单一个新元素的vector。依次即可

编辑于 2017-04-21 22:18:13 回复(0)

540485909

class Subset {
public:
	static bool comp1(const int&a, const int &b)
	{
		return a>b;
	}
	static bool comp2(const vector<int> &a, const vector<int> &b)
	{
		for (int i = 0; i<min(a.size(), b.size()); ++i){
			if (a[i]>b[i]) return true;
            else if (a[i]<b[i]) return false;
                else continue;
		}
		if (a.size() > b.size())return true;
		else return false;
	}
	vector<vector<int> > getSubsets(vector<int> A, int n) {
		// write code here
		vector<vector<int> >result;
		vector<int> cur;
		bfs(result, cur, A, 0);
		for (int i = 0; i<result.size(); ++i)
		{
			sort(result[i].begin(), result[i].end(), comp1);
		}
		sort(result.begin(), result.end(), comp2);
		return result;
	}
	void bfs(vector<vector<int> >&result, vector<int> &cur, vector<int> A, int index)
	{
		if (!cur.empty())
		{
			result.push_back(cur);
		}
		for (int i = index; i<A.size(); ++i)
		{
			cur.push_back(A[i]);
			bfs(result, cur, A, i + 1);
			cur.pop_back();

		}

	}
};

发表于 2016-04-19 14:10:36 回复(4)

C/C++

玖玖

思路：每一个元素有两种状态，包含或不包含。如此，可开辟一个数组，记录每个元素的状态。

题目要求逆序排序，则可从后往前递归即可。

class Subset {
public:
    vector<vector<int> > getSubsets(vector<int> A, int n) 
    {
        // write code here
        bool *b = new bool[n];
        memset(b, 0, sizeof(bool)*n);
        vector<vector<int> > result;
        myGetSubsets(A, n-1, n-1, b, result);
        return result;
    }
    
    void myGetSubsets(vector<int> &A, int start, int end, bool *b, vector<vector<int> > &result)
    {
        if(start < 0)
        {
            vector<int> r;
            for(int i = end; i >= 0; i--)
                if(b[i])
                	r.push_back(A[i]);
            if(!r.empty())            //去空集
            	result.push_back(r);
            return;
        }
        b[start] = true;             //该元素被包含
        myGetSubsets(A, start-1, end, b, result);
        b[start] = false;            //该元素不被包含
        myGetSubsets(A, start-1, end, b, result);
        
        return;
    }
};

发表于 2016-09-06 17:01:19 回复(1)

C/C++

nbgao

class Subset {
public:
    vector<vector<int> > getSubsets(vector<int> A, int n) {
        vector<vector<int>> r;
        int m = 1<<n;
        for(int i=m-1;i>=1;i--){
            vector<int> v;
            for(int j=i,k=0;j>0;j>>=1,k++){
                if(j&1)
                    v.insert(v.begin(),A[k]);             }             r.push_back(v);         }         return r;
    }
};

发表于 2019-02-28 04:15:11 回复(0)

linux_ever

class Subset {
public:
    vector<vector<int> > getSubsets(vector<int> A, int n) {
        // write code here
        vector<vector<int> > v;
        //从数组A的第一个元素开始
        getSubsets(A, v, 0);
        
        //先对内部进行排序，从大到小
        for(int i = 0; i < v.size(); ++i){
            sort(v[i].begin(), v[i].end(), greater<int>());
        }
        //再对外部进行排序，从大到小
        sort(v.begin(), v.end(), greater<vector<int> >());
        //弹出最后一个空元素数组
        v.pop_back();
            
        return v;
    }
    
    void getSubsets(vector<int> &A, vector<vector<int> > &v, int n){
        if(A.size() == n){
            return;
        }
        //如果是第一个元素，压入一个空数组和一个只有A[0]的数组
        if(n == 0){
            vector<int> temp1;
            vector<int> temp2;
            temp2.push_back(A[n]);
            v.push_back(temp1);
            v.push_back(temp2);
        }
        else{
            int size = v.size()-1;
            for(int i = 0; i <= size; ++i){
                vector<int> temp = v[i];
                temp.push_back(A[n]);
                v.push_back(temp);
            }
        }
        
        getSubsets(A, v, n+1);
    }
};

n = 1时，子集:{}, {123}

n = 2时，子集:{},{123} + {456},{123, 456}

n = 3时，子集:{}, {123}, {456}, {123, 456} + {789},{123, 789},{456, 789}, {123, 456, 789}

n=3的时候，是在n=2的所有子集和n=2时的所有子集添加上789，那么就得到了上面的子集.

获得所有子集之后再进行排序。

方法比较拙劣，目前通过是这个版本

编辑于 2016-08-01 13:26:44 回复(0)

Leomh

    vector<vector<int> > getSubsets(vector<int> A, int n) {
        vector<vector<int>>ans;
        sort(A.begin(),A.end(),greater<int>());
        vector<int>res;
        dfs(ans,res,A,0,n);
        sort(ans.begin(),ans.end(),greater<vector<int>>());
        return ans;
    }
    void dfs(vector<vector<int>>&ans,vector<int>res,vector<int>A,int begin,int n){
        if(begin == n)return;
        for(int i=begin;i<n;++i){
            res.push_back(A[i]);
            ans.push_back(res);
            dfs(ans,res,A,i+1,n);
            res.pop_back();
        }
    }

发表于 2019-09-01 22:08:30 回复(0)

枫叶嘟嘟左卫门

采用迭代相加的方法。

一开始初始化只有一个空集的一位数组元素的二维数组变量vector<vector<int> > vs(1)，这个空变量是有用的，可以单独存放当前遍历到的给定数组元素。举个例子如下:

给定的数组从小到大排序：{1，2，3}

①{ }

②{ } + {1}

③{ }, {1} + {2} + {1, 2}

④{ }, {1}, {2}, {1, 2} + {3}, {1, 3}, {2, 3}, {1, 2, 3}

class Subset

{

public:

vector<vector<int> > getSubsets(vector<int> A, int n)

{

vector<vector<int> > vs(1);

for (int i = 0; i < A.size(); ++i)

{

//在当前二维数组的每个一位数组元素中插入当前的目标数组元素

//然后依次追加到vs中

int size = vs.size();

for (int j = 0; j < size; ++j)

{

vs.push_back(vs[j]);

vs.back().push_back(A[i]);

}

//先内部排序，从大到小

for(int i = 0;i < vs.size();i++)

sort(vs[i].begin(),vs[i].end(),greater<int>());

//总体排序，从大到小

sort(vs.begin(),vs.end(),greater<vector<int> >());

//弹出最后一个空的一位数组元素

vs.pop_back();

return vs;

}

};

发表于 2019-08-14 20:44:19 回复(0)

Python

你回家了我在等你呢

# -*- coding:utf-8 -*-
class Subset:
def __init__(self):
self.res = []
self.Li = []

# 返回二维[[],[],[]]
def subgetSubsets(self, A, ind):
n = len(A)
#print(ind,n)
if ind >= n:
if self.Li!=[]:
self.res.append(self.Li[::1])
print(self.res)
return
#print(ind)
self.Li.append(A[ind])
self.subgetSubsets(A, ind + 1)
self.Li.pop()
self.subgetSubsets(A, ind + 1)
return

def getSubsets(self, A, n):
# write code here
A.sort(reverse=True)
self.subgetSubsets(A, 0)
return self.res

发表于 2019-05-30 09:56:35 回复(0)

Python

华科平凡

python dfs solution

# -*- coding:utf-8 -*-
class Subset:
    # 返回二维[[],[],[]]
    def getSubsets(self, A, n):
        # write code here
        res = []
        A.sort()
        self.dfs(A, res, [])
        return sorted(res, key=lambda c: "".join(map(str, c)), reverse=True)

    def dfs(self, arr, res, path):
        if path != sorted(path, reverse=True):
            return
        if path:
            res.append(path)
        if not arr:
            return
        for i in arr:
            a = arr[:]
            a.remove(i)
            self.dfs(a, res, path + [i])

编辑于 2017-10-31 18:12:23 回复(0)

此广告位出租

用位向量貌似挺有趣的，只好试一下吧

public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        // write code here
        ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
		int k = (1 << (n)) - 1;
		Arrays.sort(A);
		for (int i=0; i<n/2; i++){   //从大到小
			int t = A[i];
			A[i] = A[n-1-i];
			A[n-1-i] = t;
		}
		while (k > 0){
			ArrayList<Integer> list = new ArrayList<Integer>();
			int j = 0;
			int z = 1 << (n-1);
			while (z > 0){
				if ((z&k) > 0){
					list.add(A[j]);
				}
				j++;
				z >>= 1;
			}
			lists.add(list);
			k--;
		}
		
		return lists;
    }
}

发表于 2017-08-06 16:20:05 回复(0)

Java

面什么过什么

// 因为这两个逆序，调了好久。。。
import java.util.*;

public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<ArrayList<Integer>>();
        int max = 1 << n;
        Arrays.sort(A);
        for (int k = 0; k < max; k++) {
            ArrayList<Integer> subset = convertIntToSet(k, A);
            if (subset.size() != 0) {
                allSubsets.add(0, subset);
            }
        }
        return allSubsets;
    }
    
    private ArrayList<Integer> convertIntToSet(int k, int[] A) {
        ArrayList<Integer> set = new ArrayList<Integer>();
        int index = 0;
        for (int i = k; i > 0; i >>= 1) {
            if ((i & 1) == 1) {
                set.add(0, index);
            }
            index++;
        }
        return set;
    }
}

发表于 2017-07-28 09:41:47 回复(0)

C#

JersonMa

// P0 = {}
// P1 = 3                         {}
// P2 = 3,2             3           2          {}
// P3 = 3,2,1  3,2      3,1    3    2,1    2    1
// 即每循环一轮,相当于在当前项前插入一项比当前项多出A[i]的项, 然后i+=2得到上一轮的下一项


using System.Collections.Generic;

class Subset
{
    public List<List<int>> getSubsets(int[] A, int n)
    {
        List<List<int>> list = new List<List<int>>();
        
        if (n<0 || A==null) return list;

        System.Array.Sort(A);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= list.Count; j+=2) {
                List<int> tmp = j < list.Count ? new List<int>(list[j]) : new List<int>();
                tmp.Add(A[n-1-i]);
                list.Insert(j, tmp);
            }
        }

        return list;
    }
}

发表于 2016-09-30 10:05:18 回复(0)

L0L

//递归的方式，每一个元素只有取或者不取两种状况，假如取了，那么对剩下n-1个元素递归
class Subset {
	private:
		vector<vector<int> > res;
		vector<int> velem;
		void asisSub(vector<int> &A, int inx) {
			if(inx==A.size()) {
				if(!velem.empty())
					res.push_back(velem);
				return;
			}
			asisSub(A, inx+1);
			velem.push_back(A[inx]);
			asisSub(A,inx+1);
			velem.pop_back();
		}
	public:
		vector<vector<int> > getSubsets(vector<int> A, int n) {
			sort(A.rbegin(),A.rend());
			asisSub(A,0);
			sort(res.rbegin(), res.rend());
			return res;
		}
};

编辑于 2015-10-14 16:55:21 回复(0)

scut_huajian

这题的测试用例是反过来的，789是最大 123最小，789123比789大。

发表于 2015-08-08 09:45:25 回复(0)

忆水寒

vector<vector<int> > getSubsets(vector<int> A, int n) {
        // write code here
        vector<vector<int> > vec=helper(A,0);
        sort(vec.rbegin(), vec.rend());//排序
        vec.pop_back();//弹出最后一个空的向量
        return vec;
}
    
vector<vector<int> > helper(vector<int> A,int n)//辅助函数
{
        vector<vector<int> > vec;
        if(A.size()==n)//递归出口条件
        {
            vec.push_back(vector<int>());
        }
        else
        {
            vec=helper(A,n+1);
            int item=A[n];
            vector<vector<int> > tmp;
            //vector<int>::iterator it=vec.begin();
            for(int i=0;i<vec.size();i++)//自我拷贝，将该元素加入每一个向量中
            {
                vector<int> newlist =vec[i];
                newlist.push_back(item);
                tmp.push_back(newlist);
            }
            vec.insert(vec.end(),tmp.begin(),tmp.end());//从后面插入新的
        }
        return vec;
}

发表于 2016-08-17 18:16:27 回复(0)

集合的子集

python dfs solution

问题信息

热门推荐

通过挑战的用户

相关试题