子集和问题

问题描述：

子集和问题的一个实例为〈S,t〉。其中，S={ 1 x ， 2 x ，…， n x }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得s1中的各元素之和等于c。

java代码如下：

package com.zeko.softwearDesignCompetition.algorithm;

public class TestSumOfSubset {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int orignSet[] = new int[3];
		int length = 0;
		boolean[] selected = new boolean[3];
		for(int i = 0; i < orignSet.length; i++) {
			orignSet[i] = i + 1;
		}
		
		getSubSet(orignSet, length, selected);
	}

	public static void getSubSet(int[] set, int length, boolean[] selected) {
		if(length == set.length) {
			for(int i = 0; i < set.length; i++) {
				if(selected[i]) {
					System.out.print(set[i] + " ");
				}
			}
			System.out.println();
			return;
		}
		
		selected[length] = false;
		getSubSet(set, length + 1, selected);
		selected[length] = true;
		getSubSet(set, length + 1, selected);
		      
	}
}

算法：

假设有集合S = {1,2,3,4,5}，orignSet数组存储的是S集合，selected数组存储的是每一个元素的选中状态，legth表示

当前遍历的深度，从S数组的第一个数字开始递归，首先假设第一个元素没有被选中，那么：S{1,2,3,4,5}的子集 = 

S'{2,3,4,5}的子集 + S{1,2,3,4,5}的子集中包含1的子集；则问题转化为先求出S'{2,3,4,5}的子集，再求出S{1,2,3,4,5}的

子集中包含1的子集，即把1的位置（sleected[0]）标记为false或true，标记为flase求出的是S'{2,3,4,5}的子集，标记

为true求出的是S{1,2,3,4,5}的子集中包含1的子集，然后使用相同的方法递归的求出S'{2,3,4,5}的子集和S{1,2,3,4,5}的

子集中包含1的子集。

判定结束条件是当遍历的深度length等于数组的长度orignSet.length时，此次遍历结束，打印出当前标记为true的元素，并返回。

最后

以上就是爱笑书本为你收集整理的子集和问题的全部内容，希望文章能够帮你解决子集和问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。