计算一个数有多少种相加的结果集

回溯算法

输入 一个数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

本题使用全排列的方式计算结果

    @Test
    public void teset() {
        List<String> strings = generateTogether(6);
        strings.forEach(System.out::println);
    }

    public List<String> generateTogether(int n) {
        List<String> res = new ArrayList<>();
        generate(res, "", n, n);
        return res;
    }

    //max 表示后面的i的最大值，i对应的后面为相加的值
    private void generate(List<String> res, String ans, int max, int i) {
        if (i == 0){
            res.add(ans);
            return;
        }
        for (int j = i; j > 0; j--) {
            if (max >= j) {
                generate(res, ans +" "+ j,j,i-j);
            }
        }
    }

本题扩展
计算有多少种结果

例如 上题中 6 的结果又11

1 结果为1
2的结果为2
3的结果为3

本题采用动态规划的方法
思路

   private long printResult(int n) {
        int dp[] = new int[n + 1];
        Arrays.fill(dp, 1);
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                dp[j] += dp[j - i];
            }
        }
       return dp[n];
    }