精华内容
下载资源
问答
  • Given a set of distinct integers,  ...对给定一个集合,求出这个集合所有的子集(所谓子集,就是包含原集合中的一部分元素的集合)进行了总结。 转载于:https://www.cnblogs.com/love-yh/p/7126492.html

    Given a set of distinct integers, S, return all possible subsets.

    Note:

    • Elements in a subset must be in non-descending order.
    • The solution set must not contain duplicate subsets.

     

    For example,
    If S =[1,2,3], a solution is:

    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

     题意:求数组的所有子集,子集不用如例子中那样排序

    思路:题中要求子集中非降序排列,所以要先进行排序。方法一是使用DFS遍历。如:[1,2,3] ,依次加入[ ]、[1]、[1,2]、[1,2,3]、[1,3]、[2]、[2,3]、[3]。图形化的说明参见这里。代码如下:

     1 class Solution {
     2 public:
     3     vector<vector<int> > subsets(vector<int> &S) 
     4     {
     5         vector<vector<int>> res;
     6         vector<int> midArray;
     7         sort(S.begin(),S.end());
     8         getSubsets(S,0,midArray,res);
     9 
    10         return res;    
    11     }
    12 
    13     void getSubsets(vector<int> &S,int beg,vector<int> &midArray,vector<vector<int>> &res)
    14     {
    15         res.push_back(midArray);
    16         for(int i=beg;i<S.size();++i)
    17         {
    18             midArray.push_back(S[i]);
    19             getSubsets(S,i+1,midArray,res);
    20             midArray.pop_back();
    21         }
    22     }
    23 };

     

    方法二:使用迭代法,思路:拿res中已经存在的元素和新的组合,然后重新放入res中,先给res中放入一个空元素,然后通过空元素和S中第一个元素结合放入res中,以此类推,参考了Grandyang的博客。如:[1,2,3],最开始是空集,那么我们现在要处理1,就在空集上加1,为[1],结果中位[]和[1],下面处理2,在之前的子集基础上,每个都加个2,可以分别得到[2],[1, 2],那么现在所有的子集合为[], [1], [2], [1, 2],同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了,代码如下:

     1 class Solution {
     2 public:
     3     vector<vector<int> > subsets(vector<int> &S) 
     4     {
     5         vector<vector<int>> res(1); //放入空
     6         if(S.size()) return res;
     7         sort(S.begin(),S.end());
     8 
     9         for(int i=0;i<S.size();++i)
    10         {
    11             int midSize=res.size();
    12             for(int j=0;j<midSize;++j)  //实时结合
    13             {
    14                 res.push_back(res[j]);
    15                 res.back().push_back(S[i]);
    16             }
    17         }
    18 
    19         return res;
    20     }
    21 };

     

    在牛客网上,之前通过,现在显示如下,吐槽一下。

     Felix对给定一个集合,求出这个集合所有的子集(所谓子集,就是包含原集合中的一部分元素的集合)进行了总结。

    转载于:https://www.cnblogs.com/love-yh/p/7126492.html

    展开全文
  • 大致的思路也是相同的,先是对给定整数进行排序,这样就可以保证所求的子集都是非降序的;在循环或递归的过程中跳过重复的。DFS法的代码如下: 1 class Solution { 2 public : 3 vector int > > ...

    Given a collection of integers that might contain duplicates, S, return all possible subsets.

    Note:

    • Elements in a subset must be in non-descending order.
    • The solution set must not contain duplicate subsets.

     

    For example,
    If S =[1,2,2], a solution is:

    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]
    

     题意:可能有重复的元素,返回所有子集。

    思路:这题是subsets的扩展。大致的思路也是相同的,先是对给定整数进行排序,这样就可以保证所求的子集都是非降序的;在循环或递归的过程中跳过重复的。DFS法的代码如下:

     1 class Solution {
     2 public:
     3     vector<vector<int> > subsets(vector<int> &S) 
     4     {
     5         vector<vector<int>> res;
     6         vector<int> midArray;
     7         sort(S.begin(),S.end());
     8         getSubsets(S,0,midArray,res);
     9 
    10         return res;    
    11     }
    12 
    13     void getSubsets(vector<int> &S,int beg,vector<int> &midArray,vector<vector<int>> &res)
    14     {
    15         res.push_back(midArray);
    16         for(int i=beg;i<S.size();++i)
    17         {
    18             midArray.push_back(S[i]);
    19             getSubsets(S,i+1,midArray,res);
    20             midArray.pop_back();
    21 
    22             while(S[i]==S[i+1]) //跳过重复的元素
    23                 i++;
    24         }
    25     }
    26 };

     

    迭代法:代码来源Grandyang的博客。其主要思路是,定义变量last记录下有重复的开始,因为第一个重复的元素,已经和之前res中的区间形成新的一部分,第二或其以后的重复元素,只要和新形成的部分结合就好,因为之前的已经结合过了。代码如下:

     1 class Solution {
     2 public:
     3     vector<vector<int> > subsets(vector<int> &S) 
     4     {
     5         vector<vector<int>> res(1);
     6         if(S.size()==0) return res;
     7 
     8         sort(S.begin(),S.end());
     9         int size=res.size();
    10         if(S.size()==0) return res;
    11         int last=S[0];
    12 
    13         for(int i=0;i<S.size();++i)
    14         {
    15             if(last !=S[i])
    16             {
    17                 last=S[i];
    18                 size=res.size();
    19             }
    20 
    21             int newSize=res.size();
    22             for(int j=newSize-size;j<newSize;++j)
    23             {
    24                 res.push_back(res[j]);
    25                 res.back().push_back(S[i]);
    26             }
    27         }
    28         return res;
    29     }
    30 };

     

    转载于:https://www.cnblogs.com/love-yh/p/7126813.html

    展开全文
  • Leetcode Subsets 求数组的所有子集
                   

    Given a set of distinct integers,  S , return all possible subsets.

    Note: 

    • Elements in a subset must be in non-descending order.
    • The solution set must not contain duplicate subsets.

    For example, 
    If  S  =  [1,2,3] , a solution is:

    [  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]
    本文总结了三种思路来求数组的子集集合。前两种思路虽然都基于递归,但是出发点略有不同;后一种思路基于位运算,但是对于原数组的数量有限制。

    1.基于DFS的递归

    原数组中每一个元素在子集中有两种状态:要么存在、要么不存在。这样构造子集的过程中每个元素就有两种选择方法:选择、不选择,因此可以构造一颗二叉树来表示所有的选择状态:二叉树中的第i+1层第0层无节点表示子集中加入或不加入第i个元素,左子树表示加入,右子树表示不加入。所有叶节点即为所求子集。因此可以采用DFS的递归思想求得所有叶节点。 

    代码如下:

    //S为原数组,temp为当前子集,level为原数组中的元素下标亦为二叉树的层数,result为所求子集集合void subsets(vector<int> &S,vector<int> temp,int level,vector<vector<int> > &result)  {    //如果是叶子节点则加入到result中    if(level == S.size())    {      result.push_back(temp);      return;    }    //对于非叶子节点,不将当前元素加入到temp中    subsets(S,temp,level + 1,result);    //将元素加入到temp中    temp.push_back(S[level]);    subsets(S,temp,level + 1,result);  }
    2.基于同质的递归

    只要我们能找到比原问题规模小却同质的问题,都可以用递归解决。比如要求{1, 2, 3}的所有子集,可以先求{2, 3}的所有子集,{2, 3}的子集同时也是{1, 2, 3} 的子集,然后我们把{2, 3}的所有子集都加上元素1后(注意排序),又得到同样数量的子集, 它们也是{1, 2, 3}的子集。这样一来,我们就可以通过求{2, 3}的所有子集来求 {1, 2, 3}的所有子集了。即为求1,2,3的子集,要先求2,3的子集,然后再把1加入到2,3的子集中去,典型的递归思路。代码如下: 

    vector<vector<int> > subsets(vector<int> &S,int idx,int n)  {    vector<vector<int> > result;    if(idx == n)    {      vector<int> temp;      result.push_back(temp);    }    else    {      vector<vector<int> > vec = subsets(S,idx + 1,n);      int a = S[idx];      for(int i = 0; i < vec.size();i++)      {        vector<int> v = vec[i];        result.push_back(v);        v.push_back(a);        sort(v.begin(),v.end());        result.push_back(v);      }    }    return result;  }
    3.位运算

    求子集问题就是求组合问题。数组中的n个数可以用n个二进制位表示,当某一位为1表示选择对应的数,为0表示不选择对应的数。

    vector<vector<int> > subsets(vector<int> &S,int n)  {     //n个数有0~max-1即2^n中组合,1<<n表示2^n    int max = 1<<n;    vector<vector<int> >result;    for(int i = 0;i < max;i++)    {      vector<int> temp;      int idx = 0;      int j = i;      while(j > 0)      {        //判断最后一位是否为1,若为1则将对应数加入到当前组合中        if(j&1)        {          temp.push_back(S[idx]);        }        idx++;        //判断了这一位是否为1后要右移        j = j>>1;      }      //判断完了一种组合,加入到结果集中      result.push_back(temp);    }    return result;  }
    转载网址:http://www.tuicool.com/articles/J3En2e
               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • 遍历数组的所有子集

    2019-10-12 16:23:33
    问题如题,求数组所有子集,如items = [1, 2, 3, 4, 5],求所有items的子集 方法一:二进制,思想是n个元素的所有自己有2**n个,而n 位数的二进制数刚好也有2 ** n个,遍历n位数的所有二进制排序,0代表存在,1...

     

     

    问题如题,求数组的所有子集,如items = [1, 2, 3, 4, 5],求所有items的子集

    方法一:二进制,思想是n个元素的所有自己有2**n个,而n 位数的二进制数刚好也有2 ** n个,遍历n位数的所有二进制排序,0代表存在,1代表不存在

    def PowerSetBinary(items):
        n = len(items)
        s = np.array(items)
        for i in range(2**n):
            e = list(bin(i))[2:]
            print('before e:', e)
            e = np.array(e) == '1'
            print('=======================')
            print('after e:', e)
            print(s[n-len(e):][e])

    部分结果如下,选出来结果为True的元素 

    before e: ['0']
    =======================
    after e: [False]
    []
    before e: ['1']
    =======================
    after e: [ True]
    [5]
    before e: ['1', '0']
    =======================
    after e: [ True False]
    [4]
    before e: ['1', '1']
    =======================
    after e: [ True  True]
    [4 5]
    before e: ['1', '0', '0']
    =======================
    after e: [ True False False]
    [3]
    

    方法二:遍历  思想:元素每增加一个,子集为新加的元素与原来子集的组合再加上原来的子集

    item为1时 子集为[[],[1]]

    item为[1,2]时  新的子集为原来的子集+[2]  即[[2],[1,2]],在加上原来的子集[[],[1]],以此类推

    def PowerSetRecursive(items):
        result = [[]]
        for x in items:
            result.extend([subset + [x] for subset in result])
            print('========', result)
        print(result)
        return result

    部分结果为

    ======== [[], [1]]
    ======== [[], [1], [2], [1, 2]]
    ======== [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

     

     

    展开全文
  • 计算数组的所有子集,其实是一个组合(combination)问题。 如果数组的长度为n。 我们进行 k = 0, 1, 2, ... n 组合。将所有结果合在一起就可以了。 不熟悉组合实现朋友看这里:...
  • Subset求数组的所有子集 Description Given a set of distinct integers, S , return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not ...
  • 在一些特殊情况下我们会想要得到某一个数组的所有子集,但是原生js里没有对应方法,这就需要自己去进行处理了,如下面函数就会返回一个数组的所有子集。 allSubSets (arr) { let res = [[]] for (let i = 0; i...
  • 题目:给定一个数组arr[]={1,2,3} 打印此数组的所有子集 我绘制了一颗子集树,方便于找出所有子集及对程序进行理解,将子集树中节点左子树设为0,表示可以打印。右子树设为1,表示不打印。 package childtree; /...
  • 打印出一个元素不重复的数组的所有子集1.1 代码1.2 思路1.3 总结 1.打印出一个元素不重复的数组的所有子集 1.1 代码 递归打印子集: fun printSubset(aimedArray: IntArray, index: Int = 0, subset: MutableList...
  • 数组的所有子集

    2021-04-13 15:13:24
    子集:【1】【2】【4】【1,2】【1,4】【2,4】【1,2,4】 import java.util.ArrayList; import java.util.Collections; public class 数组序列 { public static void main(String[] args) { int[] ...
  • 数组的所有子集

    2019-01-01 16:52:45
    // pos+1 是有重复 i+1 是一直往上走 temp.pop_back(); } } };   方法2 void subsets(vector<int> &S,vector<int> temp,int level,vector<vector<int> > &result) { //如果是叶子节点则加入...
  • 求一个数组的所有子集

    千次阅读 2018-03-19 19:38:47
    求一个数组的所有子集(不考虑顺序)代码:def fun(items): result = [[]] for x in items: result.extend([ss + [x] for ss in result])#list合并,一一合并 #print(result) return result #输入元素 A=[] #A...
  • 给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 解题步骤: 该题目和寻找数组元素所有子集类似,只是需要加上一个去重条件。 方法一:采用BFS ...
  • Java数组的所有子集

    2020-07-26 17:22:20
    import java.util.ArrayList; import java.util.List; public class Subarray { public static void main(String[] args) { int[] nums = new int[]{1,2,3,4}; List<List<Integer>...s.
  • 题目是:给一个看这篇博客得到了思路:巧用递归求字符串的子集基本思想就是:求子集,每一位都只有两种状态,在子集中或不在子集中。那把每种情况都输出就可以了。import java.util.HashSet;import java.util....
  • 求解数组的所有子集

    2015-12-26 23:54:57
    题目:试编写一个递归函数,用来输出n个元素的所有子集。例如,三个元素(a,b,c)的所有子集为{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}. #include using namespace std; void SubElements(char *arr,int *...
  • 【编程题】求数组的所有子集(java实现) 题目描述 求不含重复元素的数组的所有子集 样例 输入 {1,8,5,4,6,7} 输出 [] [1] [1, 4] [1, 4, 5] [1, 4, 5, 6] [1, 4, 5, 6, 7] [1, 4, 5, 6, 7, 8] [1, 4, 5, 6, 8] [1, ...
  • 打印一个含有重复元素数组的所有子集。例如:[1,2,2]的所有子集为[[],[1],[1,2],[1,2,2],[2],[2,2]]。1、递归求解List<List<Integer>> list=new ArrayList<List<Integer>>(); public List<List<Integer>> ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,118
精华内容 847
关键字:

数组所有的子集