原题链接:http://oj.leetcode.com/problems/subsets/求子集问题是经典的NP问题,复杂度上我们就无法强求了哈,肯定是非多项式量级的。一般来说这个问题有两种解法:递归和非递归。我们先来说说递归解法,主要递推关系就是假设函数返回递归集合,现在加入一个新的数字,我们如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集,然后放入原有集合中(原来的集合中的元素不用删除,因为他们也是合法子集)。而结束条件就是如果没有元素就返回空集(注意空集不是null,而是没有元素的数组)就可以了。时间和空间都是取决于结果的数量,也就是O(2^n),代码如下:public ArrayList<ArrayList<Integer>> subsets(int[] num) {
if(num == null)
return null;
Arrays.sort(num);
return helper(num, num.length-1);
}
private ArrayList<ArrayList<Integer>> helper(int[] num, int index)
{
if(index == -1)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> elem = new ArrayList<Integer>();
res.add(elem);
return res;
}
ArrayList<ArrayList<Integer>> res = helper(num,index-1);
int size = res.size();
for(int i=0;i<size;i++)
{
ArrayList<Integer> elem = new ArrayList<Integer>(res.get(i));
elem.add(num[index]);
res.add(elem);
}
return res;
}
其实非递归解法的思路和递归是一样的,只是没有回溯过程,也就是自无到有的一个个元素加进来,然后构造新的子集加入结果集中,代码如下:public ArrayList<ArrayList<Integer>> subsets(int[] S) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
res.add(new ArrayList<Integer>());
if(S == null || S.length == 0)
return res;
Arrays.sort(S);
for(int i=0;i<S.length;i++)
{
int size = res.size();
for(int j=0;j<size;j++)
{
ArrayList<Integer> item = new ArrayList<Integer>(res.get(j));
item.add(S[i]);
res.add(item);
}
}
return res;
}
这种NP问题算法上都没有什么大的提高,基本上就是考察对于递归和非递归解法的理解,都是和N-Queens一个套路,掌握之后就没什么难度哈。
分享到:
相关推荐
subsets: 78 - permutation - combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 -...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
分类子集Web应用程序 目录 国际化 会话存储 错误处理 快取 基本文件结构 后端 部署方式本地主机 配置React脚本 整合与依存关系 ... GET /subsets GET /subsets/{subsetId}/ GET /subsets/{subsetId}/vers
此应用程序使用递归回溯的概念打印字符串的所有子集。 基本上,在这段代码中,我维护了一个数组,其中包含 0 和 1 的所有可能组合。 并且数组的长度等于字符串的长度。 现在,考虑到对于子集,要么选择字母,要么不...
leetcode 1004 leetcode 题目分类 数组 哈希表 链表 堆 栈 队列 字符串 树 Trie BST 图 最小(大)堆 Two Points 滑动窗口 递归 回溯 动态规划 排序 拓扑排序 二分查找 数学 深度优先搜索 ...Subsets
leetcode安卓The_LeetCode_Awakens Notice Naming Rule 资料夹 请把题号(三码) 放在题目前面,并用"_" 隔开,题目中间有空格,请用“-” 隔开 (ex: 078_Subsets) 题号请参考 如果没有题号,就先省略 档案 Owner 整理...
997 leetcode c 保持饥饿,保持愚蠢 我自己的 leetcode 纯 c 解决方案。 去做: 使用哈希表更新 ...78-subsets.c。 (完毕) 使用动态规划更新 qn 494-target-sum.c。 (完毕) 使用位操作更新 289-game-
用于训练所有子集的python脚本
关于Banach空间中的超弱紧子集和其等价性,程立新,程庆进,类比于Banach空间中的弱紧集和超自反空间中子集的性质,本文目的是讨论Banach空间中凸和非凸子集的超弱紧性质。作为结果,本文给出了超�
As single-layer feed-forward neural networks, extreme learning machine (ELM) has recently been used with success for the classification of hyperspectral images (HSIs). However, the results of pure ...
The CIFAR-10 and CIFAR-100 are labeled subsets of the 80 million tiny images dataset. They were collected by Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset The CIFAR-10 dataset...
%SubSets SubSets(m,n) 返回一个 n 成员集的所有 m 维子集。 % Subsets(m,n,k) 从第 k 个成员开始。 % 这个例程递归地工作。 结果按列排列% 在矩阵中。
3- All the dialect(方言的) regions should be represented in both subsets, with at least 1 male and 1 female speaker from each dialect. 4- The amount of overlap of text material in the two subsets...
指向matlab代码选择具有代表性的小插曲子集来调查道德判断的多个方面 该存储库包含 Kruepke 等人使用的 Matlab 代码。 (2018) 从 Knutson 等人创建的 ...个特征中的每一个选择一个标记为“低”、“中等/中性”和“高”...
var subsets = require ( 'subsets' ) ; var checks = 0 ; var sets = subsets ( [ 1 , 10 , 4 , 25 , 26 , 6 ] , function ( a , b ) { checks ++ ; return Math . abs ( a - b ) <= 3 ; } ) ; console . log ...
,n} into four subsets N-J, j= 1,2,3,4, according to different external input ranges, we can conclude that the HONNs have exact 3(#N2) equilibrium points, 2(#N2) of them are locally stable and others ...
Banach空间的一致凸子集,程庆进,,本文在Banach空间中引入了一致凸集的概念,其可视作一致凸Banach空间的局部化概念,证明了每个一致凸集具有许多良好的性质,例如,每个有�
The CIFAR-10 and CIFAR-100 are labeled subsets of the 80 million tiny images dataset. They were collected by Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. 官网下载速度过慢
实施:C | C ++ | JS | PHP | Python | 去吧Ruby