首先,编写一个递归算法来返回所有分区,包括那些包含重复的分区。
其次,编写一个算法来消除包含重复元素的分区。
编辑:
您可以通过避免对已经看到的数字进行递归调用来避免重复的结果。伪代码:
Partitions(n, alreadySeen)
1. if n = 0 then return {[]}
2. else then
3. results = {}
4. for i = 1 to n do
5. if i in alreadySeen then continue
6. else then
7. subresults = Partitions(n - i, alreadySeen UNION {i})
8. for subresult in subresults do
9. results = results UNION {[i] APPEND subresult}
10. return results
编辑:
您还可以避免多次生成相同的结果。通过修改循环的范围来做到这一点,这样您就只能以单调递增的方式添加新元素:
Partitions(n, mustBeGreaterThan)
1. if n = 0 then return {[]}
2. else then
3. results = {}
4. for i = (mustBeGreaterThan + 1) to n do
5. subresults = Partitions(n - i, i)
6. for subresult in subresults do
7. results = results UNION {[i] APPEND subresult}
8. return results