求自然数拆分成若干数相加形式的所有组合
【问题描述】输入自然数n，然后将其拆分成由若干数相加的形式，参与加法运算的数可以重复。【输入】待拆分的自然数n。【输出】若干数的加法式子。【样例输入】7【样例输出】1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
7
回溯法：
import java.util.ArrayList;public class Ncaifen {private static final int N = 7;public static void main(String[] args) {ArrayList<Integer> arr = new ArrayList<Integer>();//保存数字序列go(N, arr);}static void go(int m, ArrayList<Integer> arr) {if (m == 0 && arr.size() > 1) {printArr(arr);return;}for (Integer i = 1; i <= m; i++) {if (!arr.isEmpty() && i < arr.get(arr.size() - 1))continue;arr.add(i);go(m - i, arr);arr.remove(i);}}private static void printArr(ArrayList<Integer> arr) {// TODO Auto-generated method stubfor (int i = 0; i < arr.size(); i++) {System.out.print(arr.get(i));if (i < arr.size() - 1)System.out.print("+");}System.out.println();}}