题目：把一个正整数n拆分成若干个正整数的相加，列出所有组合 例如：
4=4
4=1+3=2+2
4=1+1+2
4=1+1+1+1
动机：网上有好多解答，大部分都是给出拆分结果的个数，不能把把每一种的情况打印出来，或者效率低，本人接触这个题目很久了，最近心血来潮想搞定它，嘿嘿
思路一：
设置一个递归方法recursive(int last, int curSum, int n)，该方法包含以下几个步骤：
0. 递归出口: 当 last+curSum > n ,返回
1. 该递归方法包含三个参数
a. last：上个递归传递给它的起始数字
b.curSum:当前累加和
c. n:待拆分的数字
2. 设置变量i从last开始到n遍历：
a. curSum=curSum+i;
b. list(成员变量)加入i
c. 判断curSum==n ,如果成立，打印list
3. 递归调用 recursive(i, curSum,n);
4. 还原curSum,list，消除下一层递归对本层递归在成员变量curSum,list的影响。
实现代码
package com.uestc.miaoshi;
import java.util.ArrayList;
import java.util.Scanner;
public class BreakN2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
count = 0;
recursive(1, 0 , n);
System.out.println("所有组合总数" + count);
}
}
static int count = 0;
static ArrayList<Integer> list = new ArrayList<>();
static void recursive(int last, int curSum, int n) {
if (last + curSum > n) return;
for (int i = last; i <= n ; i++) {
curSum = curSum + i;
list.add(i);
if (curSum == n) {
count ++;
System.out.println(list);
}
recursive(i, curSum, n);
curSum = curSum - i;
Integer o = i;
list.remove(o);
}
}
}
输入 5 ,打印出以下结果：
这种思路的优点是容易思考，缺点是当n很大时，耗时大，归根是算法效率低。下面我们继续介绍一种效率高的解决方法。
思路二：动态规划，设置一个函数 f(n, m) ,该函数的功能就是把正整数分成 m等分， 并且m 份中不允许为0，也就是说每一份至少大于等于1. 我们可以得到状态转移方程:
f(n ,m ) = f(n-m,m) + f(n-1, m-1)
看到这里如果，你能经过自己的思考就明白这个公式，我只能膜拜，因为你的天赋很高，哈哈，好了，言归正传。
方程的第一项 f(n-m, m) 代表m份全部都大于1的分法，也可以这样理解，先把 m 拆分成 m 个 1 ，每一份都是1 ，然后 再把 n - m 分到 m 份中
方程的第二项是 f(n-1, m-1)代表至少存在一份为1的情况，那么怎么保证呢？先从n中拿出1，放到m份中的1份，然后把 n-1分到 m-1份
总结： f(n,m)=f(n-m, m)不包含1的组合+f(n-1, m-1)包含1的组合，一分为二的思想
实现代码：
package com.uestc.miaoshi;
import java.util.Scanner;
public class BreakN {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
long start = System.currentTimeMillis();
int res = 0;
int n = sc.nextInt();
for (int i = 1; i <= n; i++) {
res = res + f(n, i);
}
System.out.println("总共组合数: " + res);
long end = System.currentTimeMillis();
System.out.println("耗时秒数:"+ (end - start)/1000);
}
}
/**
* 函数功能，把正整数 n 分成 m 等份 4 = 1+3 = 2+2
* @param n
* @param m
* f(n) = f(n-m, m) + f(n-1, m-1)
*/
private static int f(int n, int m) {
if ( n <=0 || m <= 0 || n < m) {
return 0;
}
if (m == 1) return 1;
return f(n - m, m) + f(n-1, m-1);
}
}
其实说到这里我们只是把问题解决了一半，我们可以轻松的得出所有组合的总数，我们还不能把每一种组合的具体情况打印出来。咋办呢，山人自有妙计。
思路我就照着下面这个图讲吧
首先定义树的数据结构：
class TreeNode {
int n, m;
ArrayList<Integer> res = new ArrayList<>();
boolean addAll;
TreeNode left, right, parent;
public TreeNode(int n, int m, boolean addAll) {
this.n = n;
this.m = m;
this.addAll = addAll;
}
}
addAll =false表示f(n-1, m-1)， 也就是代表m份包含1的分法,由下而上回溯时，上结点的res=下结点的res加上一个元素1
addAll =true表示f(n-m, m)， 也就是代表m份不包含1的组合的分法，由下而上回溯时，上结点的res=下结点的res每个元素加上1
res表示具体的分法
我们可以把图看成是二叉树的升级版本(每一个节点都有父指针)，叶子节点表示具体的分法，比如f(1,1) = 1 ,f(3,1)=3。
我们可以从叶子结点回溯到根结点，例如
f(1,1) = 1, addAll=false,向上回溯到f(2,2)结点，导致f(2,2)结点的res =[1,1]
f(2,2),res=[1,1],addAll=true,向上回溯到f(4,2)结点，导致f(4,2)结点的res=[2,2]
f(3,1),res=[3],addAll=false,向上回溯到f(4,2)结点，导致f(4,2)结点的res=[1,3]
下面看具体实现代码：
package com.uestc.miaoshi;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class TreeNode {
int n, m;
ArrayList<Integer> res = new ArrayList<>();
boolean addAll;
TreeNode left, right, parent;
public TreeNode(int n, int m, boolean addAll) {
this.n = n;
this.m = m;
this.addAll = addAll;
}
}
public class BreakNToM {
static ArrayList<TreeNode> leafs = new ArrayList<>();
static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
long start = System.currentTimeMillis();
int n = in.nextInt();
int m = in.nextInt();
leafs.clear();
f(n, m, true);
for (TreeNode leaf : leafs) {
recursive(leaf);
}
long end = System.currentTimeMillis();
System.out.println( (end - start)/1000);
System.out.println(result);
}
}
private static void recursive(TreeNode leaf) {
if (leaf.parent == null) {
Collections.sort(leaf.res);
result.add(leaf.res);
return;
}
ArrayList<Integer> res = leaf.res;
if (leaf.addAll) {
ArrayList<Integer> temp = new ArrayList<>();
for (int x : res) {
temp.add(x + 1);
}
leaf.parent.res = temp;
} else {
res.add(1);
leaf.parent.res = res;
}
recursive(leaf.parent);
}
static TreeNode f(int n, int m, boolean allAdd) {
if (n < m || n <= 0 || m <= 0) {
return null;
}
TreeNode node = new TreeNode(n, m, allAdd);
if (n == m) {
TreeNode leaf = new TreeNode(n, n, allAdd);
for (int i = 0; i < m; i++) {
leaf.res.add(1);
}
leafs.add(leaf);
return leaf;
}
if (m == 1) {
TreeNode leaf = new TreeNode(n, 1, allAdd);
leaf.res.add(n);
leafs.add(leaf);
return leaf;
}
node.left = f(n - m, m, true);
if (node.left != null)
node.left.parent = node;
node.right = f(n - 1, m - 1, false);
if (node.right != null)
node.right.parent = node;
return node;
}
}
输入 8 3
搞定