求java用回溯法解决子集和有关问题

求java用回溯法解决子集和问题
子集和问题:
问题描述:子集和问题的一个实例为<S,t>.其中,S={X1,X2,X3,……，XN}是一个正整数的集和，C是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中的所有元素加起来正好等于C。
试设计一个解子集和问题的回溯法。
算法设计：对于给定的   S={X1,X2,X3,……，XN}和正整数C，计算S1，使得S1中的所有元素加起来正好等于C。
数据输入：从键盘输入两行数据，第一行有1个正整数C， C是子集和的目标值。接下来一行中有N个正整数，表示集合S中的元素。
结果输出：将子集和问题的所有解输出。当问题无解时，输出“No Solution！”
如：输入： 10 
           2   2   6  5  4
输出：2  2  6
      6   4

------解决思路----------------------

package com.huisu;

public class Main {
	public static void main(String[] args) {
		int[] input = {6,4,2,2,5,6,1};
		int[] record = new int[input.length];
		int key = 10;
		backtrack(input, record, key, 0, 0);
	}

	public static void backtrack(int[] input,int[] record,int key,int sum,int n) {
		if(n == input.length){
			return;
		}else{
			for(int i=0; i<=1; i++){
				sum += i*input[n];
				record[n] = i;
				if(sum == key){
					for(int j=0; j<=n; j++){
						if(record[j]==1)
							System.out.print(input[j]);
					}
					System.out.println();
				}
				if(sum<key){
					backtrack(input, record, key, sum, n+1);
				}
				sum -= i*input[n];
			}
		}
	}
}

//output
226
2251
46
451
622
64

输入就简单点了，不写scanner了