递归、动态规划、回溯法解决整数划分问题，并输出所有划分情况

整数的分划问题。
如，对于正整数n=6，可以分划为：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
现在的问题是，对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。

递归算法

在正整数a的不同划分中，将最大加数n不大于m的划分个数记为q(n,m)。
可以建立q(n,m)如下的关系。

1. q(n,1) = 1,n>=1.最大加数不大于1 此时划分为n=1+1+…+1;
2. q(n,m) = q(n,n)，m>=n.最大加数不能大于n；
3. q(n,n) = 1+q(n,n-1) 此时只有 n=n 和最大加数不大于n-1的划分
4. q(n,m) = q(n,m-1)+q(n-m,m) n>m>1.此时n不大于m的划分由n不大于m-1的划分，和n-m不大于m的划分组成。

public int q(int n, int m) {
		if (n < 1 || m < 1) 
			return 0;
		if (n == 1 || m == 1) 
			return 1;
		if (n < m)
			return q(n, n);
		if (n == m) 
			return q(n, m - 1) + 1;
		return q(n, m - 1) + q(n - m, m);
	}

结果

动态规划算法

首先构建dp数组用于记录每种划分的值。将最大加数n不大于m的划分个数记为dp[i][j]。先进行初始化将d[1][j]和dp[i][1]为1。
然后从dp[2][2]开始

1. 如果j>i，dp[i][j]=dp[i][i];
2. 如果i=j，dp[i][j] =1+dp[i][j-1];
3. 如果i<j，dp[i][j]=dp[i][j-1]+dp[i-j][j];

	public static void IntPart(int n) {
		int [][]dp = new int [n+1][n+1];
		for(int i=1;i<=n;i++) {
			dp[1][i] = 1;
		}
		for(int i=1;i<=n;i++) {
			dp[i][1]=1;
		}
		for(int i=2;i<=n;i++) {
			for(int j=2;j<=n;j++) {
				if(j>i) dp[i][j]=dp[i][i]; 
				else if(i==j) dp[i][j] =1+dp[i][j-1];
				else {
					dp[i][j]=dp[i][j-1]+dp[i-j][j];
				}
			}
		}
		for(int x1[]:dp) {
			for(int x2:x1) 
				System.out.print(x2+" ");
			System.out.println();
		}
	}

dp[n][n]即为划分总数
结果

以上两种算法本质上相同，但是都只能输出个数，不能输出全部序列。下面采用回溯法输出全部序列。

回溯法

首先全局变量nums数组和count分别记录划分和划分个数
函数 integerDivide(int cur,int sum,int p,int n)有四个变量cur记录当前数组使用了几个位置，sum为当前划分相加的和，p为此时的划分最大的值，n为需要划分的数。
如果递归参数sum大于n说明此条支路走不通，就return将它剪掉。
如果相等就输出结果。
用for循环，从i=p开始每次减一，nums数组添加i，然后此时递归求解 integerDivide(cur+1,sum+i,i,n) 表面cur位置加一，总和sum加最大可划分的数，最大可划分的数变为i。
假设n为6，第一次递归的for循环会i从6到1之后递归求解各条支路。

public class IntegerDivide {
    int []nums = new int[20];
    int count = 0;
    public void integerDivide(int cur,int sum,int p,int n){
        if(sum > n) return;
        if(sum == n){
            count++;
            System.out.print(n+"=");
            for (int i = 0; i < cur; i++) {
                if (i==cur-1)
                    System.out.print(nums[i]);
                else System.out.print(nums[i]+"+");
            }
            System.out.println();
            return;
        }
        for (int i=p;i>0;i--){
            nums[cur] = i;
            integerDivide(cur+1,sum+i,i,n);
        }
    }
    public static void main(String args[]){
        IntegerDivide i = new IntegerDivide();
        i.integerDivide(0,0,6,6);
        System.out.println(i.count);
    }
}

结果