算法练习之整数分割问题-白红宇

算法练习之整数分割问题

阅读量：5880 次

发布时间：2019-06-19

本文共 1076 字，大约阅读时间需要 3 分钟。

整数分割问题是这样的：

将一个正整数分割成一系列整数的和。

如：

5 = 4 + 1

5 = 3 + 2

5 = 3 + 1 + 1

5 = 2 + 2 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

数字顺序不重要，但不能出现重复，比如

5 = 2 + 2 + 1和5 = 2 + 1 + 2就是不能重复出现的。

之前想了很多方法，总是存在重复的项。有一个比较“笨”的方法就是用一个HashSet来保存，但总感觉不是很满意。

今天上课时，突然想到一个比较满意的方法，用Java实现如下：

1 public class SplitNum { 2     public static void main(String[] args) { 3         split(6); 4     } 5  6     public static void split(int n) { 7         split(n + " = ", n, n - 1); 8     } 9 10     /**11      * 分割数字num12      * @param pre 前缀字符13      * @param num 要分割的数字14      * @param max 最大的分割数15      */16     public static void split(String pre, int num, int max) {17         if (num <= max) {18             System.out.println(pre + num);19             for (int i = num - 1; i > 0; i--) {20                 split(pre + i + " + ", num - i, i);21             }22         } else {23             for (int i = max; i > 0; i--) {24                 split(pre + i + " + ", num - i, i);25             }26         }27     }28 }