组合问题 之 罗列特定和的数字组合方式

package com.test.algorithm.dp;

import java.util.HashSet;
import java.util.Set;

/**
 * @author hawkinswang
 *
 *         01背包问题:在指定数组中挑选任意组合,让它们的和等于一个特定值,列出所有组合方式
 *         使用动态规划方法解决,状态转移方程:dp[i][j]=dp[i-arr[j]][j-1].add(arr[j])
 *
 */
public class FindComineEqualSum {
    public static void main(String[] args) {
	int[] arr = { 1, 3, 5, 7, 8, 9, 10, 2, 4, 6 };
	int sum = 11;

	Set<String> combines = findCombine(arr, sum);

	for (String combine : combines) {
	    if (combine != null) {
		System.out.println("the result is:" + combine);
	    }
	}
    }

    private static Set<String> findCombine(int[] arr, int sum) {
	Set<String> result = new HashSet<String>();
	Set<String>[][] dp = new HashSet[sum + 1][arr.length + 1];
	int i = 0, j = 0;
	for (j = 0; j < arr.length + 1; j++) {// 当求和为0时,初始化为"";非常重要,这是动态规划数组产生合理组合的基础.
	    dp[0][j] = new HashSet<String>();
	    dp[0][j].add("");
	}

	for (i = 1; i <= sum; i++) {
	    for (j = 1; j <= arr.length; j++) {
		for (int k = 0; k <= j - 1; k++) {
		    if (dp[i][k] != null && dp[i][k].size() > 0) {
			if (dp[i][j] == null) {
			    dp[i][j] = new HashSet<String>();
			}
			dp[i][j].addAll(new HashSet<String>(dp[i][k]));
		    }
		}

		if (i >= arr[j - 1] && dp[i - arr[j - 1]][j - 1] != null) {
		    if (dp[i][j] == null) {
			dp[i][j] = new HashSet<String>();
		    }

		    for (String str : dp[i - arr[j - 1]][j - 1]) {
			dp[i][j].add(str + "," + arr[j - 1]);
		    }
		}
	    }

	    // readArray(dp);
	}

	for (Set<String> Set : dp[sum]) {
	    if (Set != null) {
		result.addAll(Set);
	    }
	}

	return result;
    }

    private static void readArray(String[][] dp) {
	for (String[] arr : dp) {
	    for (String str : arr) {
		System.out.print(str + "/");
	    }
	    System.out.println();
	}
	System.out.println("end");

    }

}