Java实现生成集合的所有非空子集

/**
	 *  生成集合的所有子集(本算法中没有把空集作为子集返回，如果需要，请自行添加)
	 * 本算法采用递归实现
	 * @param sourceSet
	 * @param result
	 */
	public void buildSubSet(List<String> sourceSet, List<List<String>> result) {
                //仅有一个元素时，递归终止。此时非空子集仅为其自身，所以直接添加到result中
		if (sourceSet.size() == 1) {
			List<String> set = new ArrayList<String>();
			set.add(sourceSet.get(0));
			result.add(set);
		} else if (sourceSet.size() > 1) {
　　　　　　　　//当有n个元素时，递归求出前n-1个子集，在于result中
			buildSubSet(sourceSet.subList(0, sourceSet.size() - 1), result);
			int size = result.size();　　//求出此时result的长度，用于后面的追加第n个元素时计数
　　　　　　　　//把第n个元素加入到集合中
			List<String> single = new ArrayList<String>();
			single.add(sourceSet.get(sourceSet.size() - 1));
			result.add(single);          
                        //在保留前面的n-1子集的情况下，把第n个元素分别加到前n个子集中，并把新的集加入到result中;
　　　　　　　　//为保留原有n-1的子集，所以需要先对其进行复制
			List<String> clone;
			for (int i = 0; i < size; i++) {
				clone = new ArrayList<String>();
				for (String str : result.get(i)) {
					clone.add(str);
				}
				clone.add(sourceSet.get(sourceSet.size() - 1));

				result.add(clone);
			}
		}
	}

评论

1 楼 541732025 2010-06-28  

顶！沙发！