Calculate the partitions of N

Question

Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

These lists do not have to be output in any particular order, nor do the numbers inside each list. For example, this would also be an acceptable output for '5':

[1, 1, 1, 2]
[5]
[3, 1, 1]
[2, 1, 2]
[4, 1]
[1, 1, 1, 1, 1]
[2, 3]

You can safely assume that the input will be a positive integer, and you can take this number in any reasonable format.

You may NOT use any builtin functions that do this.

If your program either fails or takes too long for large N this is OK, but you must at the very least produce the correct output for the first 15.

Standard loopholes apply, and the shortest answer in bytes wins!

Test IO

1:
[[1]]
2:
[[1, 1], [2]]
3:
[[1, 1, 1], [1, 2], [3]]
4:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]
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]]
10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]

Super large test case: 15 should output this

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]

Catalog

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 84165; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 31716; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

• DJMcMayhem: Related: codegolf.stackexchange.com/questions/46991/…
• Dennis: Could you clarify what you mean by handle?
• user45941: @flawr I disagree - finding all partitions is sufficiently different from finding strict partitions. However, this one might be a dupe target.
• xnor: I think looking for unordered partitions and not limiting the number of parts makes this different enough.
• Leaky Nun: Can you clarify what you mean by buitin?

Answer 1

Pyth, (削除) 10 (削除ここまで) 9 bytes

{SMlMM./U

Not too sure if this isn't cheating, but the rules only said one cannot use integer partition (it's not stated clearly in the question itself, but a comment by OP in the question says integer partition). I'm using (削除) string (削除ここまで) list partition, which makes slices of the list that concatenate up to the "mother" list. I believe I have to thank @Maltysen for the idea of using lists rather than strings.

n=15 takes less than one second on my machine.

In dataflow pseudocode:

 input // initial data
 U range // makes a list of length equal to input
 ./ partition // partitions string
 lMM length // length of each substring in each way to partition
 SM sort // sort each way to partition
{ deduplicate // removes all duplicate after sorting
 print // implicit, output final result

Try it online here.

• Leaky Nun: {mSlMd./*N saves a byte
• Maltysen: You can go for 7 bytes if you use list partitioning instead of string partition: pyth.herokuapp.com/?code=sMM.%2Fm1&input=5&debug=0
• busukxuan: @LeakyNun Well I actually tried and it didn't save a byte. When I saw your comment tho, I found out that my answer was actually 10 bytes, so I actually miscounted (forgot gedit blocks start from 1).
• busukxuan: @Maltysen You need to sort each sub-list, and then deduplicate.
• busukxuan: @Maltysen You were right, using lists does shorten it. I tried adding sort and deduplicate to the code you linked to and it didn't help, but it's all thanks to you that I got the idea of replacing *N with U. Thanks!

Answer 2

Pyth, 18 bytes

L?b{SM+R-bsdsyMb]Y

Try it online! (The y at the end is used to call the function)

This is fairly quick.

This uses recursion. If the input is b, my method will generate the partitions from 0 to b-1, and then generate the correct partitions from each.

For example, when b=4:

• b=0 gives [[]]
• b=1 gives [[1]]
• b=2 gives [[2], [1, 1]]
• b=3 gives [[3], [1, 2], [1, 1, 1]]

Then, to each partition in b=0, append 4 (to make the sum 4); to each partition in b=1, append 3 (to make the sum 4); etc.

This is mainly how it works.

L?b{SM+R-bsdsyMb]Y
L define a function called "y" which takes an argument: "b"
 ?b test for truthiness of b (in this case, test if b>0).
 {SM+R-bsdsyMb if truthy:
 yMb call this function from 0 to b-1.
 s unpack each list of partitions, generating only partitions.
 +R to each partition (d), append:
 - the difference of
 b b (the argument) and
 sd the sum of d (the partition).
 SM sort each partition.
 { remove duplicates.
 ]Y if falsey:
 Y yield [].
 ] yield [[]].

Answer 3

Haskell, 53 bytes

p=[[]]:[map(1:)q++[a+1:b|a:b<-q,all(a<)b]|q<-p]
(p!!)

Answer 4

MATL, 20 bytes

:"0Gq:@XNG3$Yc!dS!Xu

Try it online!

For input 15 it takes about 2 seconds in the online compiler.

Explanation

This works by generating partition points and then converting to partition lengths. What I mean by this is the following. Given input N = 5, a possible partition is [2 2 1]. This is represented by partition points [0 2 4 5], such that consecutive differences (or lengths) of the partition points give the resulting partition of the input number.

All arrays of partition points start with 0 and end with N. The number k of intermediate points varies from 0 to N-1. For N and k given, the intermediate points can be generated as a combination of the numbers [1, 2, ..., N-1] taken k at a time.

Several arrays of partition points may give rise to the same result in a different order. For example, partition points [0 1 3 5] would give the partition lengths [1 2 2], i.e. the same as the previous [2 2 1] only in a different order. This has to be taken into account by sorting each array of partition lengths and removing duplicates.

: % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
 % except with N instead of 0
" % For each
 0 % Push 0
 Gq: % Push [1 ... N-1]. These the possible intermediate points
 @XN % Push k and produce the combinations. Each k produces a 2D array with
 % each combination on a row. The value k=N produces an empty array
 G % Push N
 3$Yc % Prepend a column of zeros and append a column of N to the array
 !d % Transpose. Consecutive differences of each column
 S! % Sort each column. Transpose
 Xu % Keep only unique rows
 % Implicitly end for and display all arrays in the stack

• Nick: Nice, the concept of partition points is a very clever way to solve this.
• Luis Mendo: @Nick Thank you! And welcome to (being active in) this site! :-)

Answer 5

J, (削除) 49 (削除ここまで) (削除) 42 (削除ここまで) (削除) 36 (削除ここまで) (削除) 35 (削除ここまで) 32 bytes

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]

It's tacit now!

Builds the integer partition of n by constructing the integer partitions from 1 to n. Computes the result for n = 15 in a millisecond.

Starting with the initial integer partition [[1]] which corresponds to n = 1, construct the next integer partition by joining the results from two operations: appending a 1 to each partition; incrementing the smallest value by 1 in each partition. Of course, duplicate partitions will be removed. To get the integer partition n = 2 and onwards,

Partition for n = 1
[[1]]
Partition for n = 2
[[1, 1]] join [[2]]
= [[1, 1], [2]]
Partition for n = 3
[[1, 2], [1, 1, 1]] join [[3], [1, 2]]
= [[3], [1, 2], [1, 1, 1]]
... and so on

Usage

 f =: a:1&([:~.@,(,;}./:~@,(+{.))&>)~]
 f 1
┌─┐
│1│
└─┘
 f 2
┌───┬─┐
│1 1│2│
└───┴─┘
 f 3
┌─────┬───┬─┐
│1 1 1│1 2│3│
└─────┴───┴─┘
 f 5
┌─────────┬───────┬─────┬───┬─────┬───┬─┐
│1 1 1 1 1│1 1 1 2│1 2 2│2 3│1 1 3│1 4│5│
└─────────┴───────┴─────┴───┴─────┴───┴─┘
 # f 15
176

Explanation

Since J does not support ragged arrays, each partition has to be boxed so they they won't be zero padded when appended to other partitions.

a:1&([:~.@,(,;}./:~@,(+{.))&>)~] Input: n
a: The empty box
 ] Get the input n
 1&( )~ Repeat n times with an initial array of one empty box
 ( )&> Operate on each partition
 ( ) Hook a partition
 {. Get its head (the smallest value)
 1 + Add 1 to it
 1 }. Drop the first value in each partition
 , Join the previous two results
 /:~@ Sort it
 1 , Prepend a 1 to the initial partition
 ; Box the last two results and join them
 [: , Flatten the pairs of boxes
 ~.@ Remove duplicates and return
 Return the final result where each box
 is a partition of n

Answer 6

Python, 65 bytes

Python 3

def f(n,i=1,l=[]):n or print(l);i>n or[f(n-i,i,[i]+l),f(n,i+1,l)]

This function accumulates a partition and prints the outputs, branching on choices. It decides how many 1's to put in the partition, how many 2's, and so on. For each value i, it either

• Adds a part of size i, and decreases n to n-i, or
• Moves on to i+1

If i>n, then no more parts can be made, so it stops. If n falls to 0, the partition is successful and so is printed.

Python 2

f=lambda n,i=1:n/i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:]

A recursive method that outputs a list of partitions. As with the Python 3 code, it counts up the part size i and decides at each step whether to add another part of size i or stop.

Both of these do n=15 almost instantly.

Answer 7

Javascript, 194 bytes

p=n=>{var a=[];for(var i=1;i<=n-i;i+=1){for(v of p(n-i)){v.push(i);a.push(v.sort())}}a.push([n]);return a};n=5;s=p(n).map(v=>JSON.stringify(v));s=s.filter((v,i)=>s.indexOf(v)==i);console.log(s);

Non-minified

Finding uniques by sorting and comparing to a string is quite a hack, but probably saves space.

p = n => {
 var a = [];
 
 for (var i = 1; i <= n-i; i++)
 {
 for (v of p(n-i)) {
 v.push(i);
 a.push(v.sort());
 }
 }
 a.push([n]);
 return a;
}
n = 5;
s = p(n).map(v => JSON.stringify(v));
s = s.filter((v,i) => s.indexOf(v) == i);
console.log(s);

• DJMcMayhem: Quite a hack but saves space That's exactly what this site is about. :D

Answer 8

Haskell, 44 bytes

0%m=[[]]
n%m=[j:r|j<-[m..n],r<-(n-j)%j]
(%1)

The auxiliary function n%m gives the partitions of n into parts ≥m, with the main function using m=1. It branches of each first entry j with m≤j≤n, recursing on the remaining partition of n-j into parts that are at least j. The base case n==0 gives just the empty partition.

Answer 9

Python 3.5, (削除) 82 (削除ここまで) 72 bytes

f=lambda n:{(*sorted([*p,i]),)for i in range(1,n)for p in f(n-i)}|{(n,)}

Returns a set of tuples. n = 15 finishes instantly.

Test it on repl.it.

Answer 10

Brachylog, 33 bytes (Non-competing)

:1f:oad.
:1eI,.##lI,.:{.>0}a+?,.=

This is non-competing because of a bug fix.

This takes about 1 second for 15 on my machine. For 20 and greater this crashes with an Out of global stack exception.

Explanation

This uses no partitioning built-in of any kind, and instead uses the fact that + works both ways through constraints propagation.

• Main predicate:

  :1f Find the list of all valid outputs of predicate 1
   :oa Sort each element of that list
   d. Output is that list of sorted lists minus all duplicates
  

• Predicate 1:

  :1eI I is an integer between Input and 1
   .##lI, Output is a list of length I
   .:{.>0}a Elements of Output are integers greater than 0
   +?, The sum of the elements of Output is Input
   .= Assign values to the elements of Output
  

Answer 11

Pyth, 17 bytes

L|{SMs+LVrb0yMb]Y

Defines a function named y. Try it online.

Answer 12

Jelly, 9 bytes

b1ŒṖḅ1Ṣ€Q

Try it online!

How it works

b1ŒṖḅ1Ṣ€Q Main link. Argument: n (integer)
b1 Convert n to unary, i.e., a list A of n 1's.
 ŒṖ Generate all partitions of the list A.
 ḅ1 Convert each flat list from unary to integer.
 Ṣ€ Sort each resulting list.
 Q Unique; deduplicate the lists.

Answer 13

J, 39 bytes

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:

This is a monadic verb that takes an integer and returns an array of boxed arrays. Try it here. Usage:

 p =: [:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:
 p 3
+-----+---+-+
|1 1 1|2 1|3|
+-----+---+-+

On input 15, it runs for about a second on my machine.

Explanation

This challenge immediately looked like a job for Catalogue ({) and Cut (;.). The outline of the algorithm is:

• Produce all 0-1 arrays of length n.
• For each of them, cut a dummy length-n array along the 1s, and list the lengths of each part.
• Sort the lengths, and remove duplicate arrays from the result.

Apparently, Luis Mendo had the same idea too.

Explanation of code:

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<: Input is n.
 <: n-1
 #~ copies of
 (<1 0) the boxed array [1 0].
 1 ; Prepend the boxed array [1].
 {@ Catalog: produces all combinations of taking one
 item from each box, in a high-dimensional matrix.
 ,@ Flatten the matrix. This results in a list of all
 boxed 0-1 arrays of length n that begin with a 1.
 i. The array A =: 0, 1, ..., n-1.
 ( "1 0) For each of the boxed arrays B:
 ;.1~ cut A along the occurrences of 1s in B,
 # take the length of each part,
 \:~@ sort the lengths,
 <@ and put the result in a box.
[:~. Remove duplicate boxes.

• miles: Very nice use of cut ;. again.

Answer 14

Mathematica, (削除) 62 (削除ここまで) 54 bytes

Inner[#2~Table~#&,FrobeniusSolve[r=Range@#,#],r,Join]&

The partitions of an integer n can be found by solving for n-tuples of non-negative integers (c₁, c₂, ..., c_n) such that c₁ + 2 c₂ + ... + n c_n = n. FrobeniusSolve is able to find all solutions to this equation which are used to create that many copies of their respective values in order to find all integer partitions of n.

• Leaky Nun: ... and how is this not a built-in?
• miles: @LeakyNun FrobeniusSolve does not find integer partitions, it finds all solutions of non-negative integers x1 ... xN to equations of the form a1 x1 + a2 x2 + ... aN xN = b given a1 ... aN and b.

Answer 15

Vyxal, 7 bytes

×ばつ'∑?=

Try it Online!

×ばつ'∑?=
ɾ # Get a list in the range [1, input]
 ×ばつ # Get all combinations (with replacement) of all lengths
 ' # Filter for:
 ∑?= # Sum equals the input

Answer 16

JavaScript (削除) (Firefox 30-57) 79 (削除ここまで) ES6, 65 bytes

f=(n,m=1,a=[])=>n?m>n?[]:[...f(n-m,m,[...a,m]),...f(n,m+1,a)]:[a]

Port of @xnor's Python solution. (If only I'd noticed that you could recurse over m as well as n...)

Answer 17

05AB1E, 8 bytes

Å1.œO€{ê

Outputs as a list of lists, from n amount of 1s to [n], where each inner list is sorted (I know the rules allow them to be unsorted, but it's necessary for the uniquify of lists).

Try it online or verify the first 15 result.

If builtins were allowed, this would be 2 bytes instead (with the same exact results):
Åœ - Try it online or verify the first 15 results.

Explanation:

Å1 # Push a list with the (implicit) input amount of 1s
 .œ # Get all partitions of this list
 O # Sum each inner-most list
 €{ # Sort each inner list
 ê # Sorted uniquify the list of lists
 # (after which the result is output implicitly)

Minor note: ê (sorted uniquify) could also just be Ù (uniquify) for the same result, but with the added sort it's a lot faster in this case.

• Kevin Cruijssen: Apparently it's the exact same approach as @Dennis' Jelly answer I now notice. I came up with it independently just yet, but it's not too surprising we're using the same straight-forward approach, being codegolf languages with these builtins available.

Answer 18

Curry (PAKCS), 44 bytes

(1!)
_!0=[]
a!n=anyOf[a ..n]#n
a#n=a:a!(n-a)

Try it online!

Answer 19

Scala, 117 bytes

Port of @Dennis's Python answer in Scala.

---

Golfed version. Try it online!

def f(n:Int):Set[Seq[Int]]=if(n==1)Set(Seq(1))else(1 until n).flatMap(i=>f(n-i).map(_:+i).map(_.sorted)).toSet+Seq(n)

Ungolfed version. Try it online!

object Main extends App{ 
 def f(n: Int): Set[List[Int]] = {
 if (n == 1) {
 Set(List(1))
 } else {
 (1 until n).flatMap { i =>
 f(n - i).map { p =>
 (p :+ i).sorted
 }
 }.toSet + List(n)
 }
 }
 println(f(15));
}