本文共 1091 字，大约阅读时间需要 3 分钟。

子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和问题

判定是否存在S的一个子集S1，使得子集S1和等于c。 设计一个回溯法来求解该问题。

解题思路：对于该集合的每一个子集，若元素和为正整数c，则将该子集放入解集中，最后返回解集即可。

/**	 * @param list 存放所有满足要求的解	 * @param tempList 存放每一轮的解	 * @param nums 正整数集合	 * @param target 目标和	 * @param start 开始位置	 * @param sum 每一个子集和	 */	public void backtrack(List
   
    
     > list, ArrayList
     
       tempList,			int[] nums, int target, int start, int sum) 	{		if (sum == target) 		// 找到一个满足条件的解		{			list.add(new ArrayList<>(tempList));		}				for (int i=start; i
      
       > list = new ArrayList<>();		ArrayList
       
         tempList = new ArrayList<>();		backtrack(list, tempList, s, target, 0, 0);				if (list.size() == 0)			System.out.println("No Solution");		else			System.out.println(Arrays.toString(list.toArray()));	}
       
      
     
    
   

也可以省去backtrack函数中的参数sum。代码如下：

public void backtrack(List
   
    
     > list, ArrayList
     
       tempList,			int[] nums, int target, int start) 	{		if (target == 0) 		// 找到一个满足条件的解		{			list.add(new ArrayList<>(tempList));		}				for (int i=start; i
     
    
   

非递归回溯法：

转载地址：http://pcpoi.baihongyu.com/