19
\$\begingroup\$

Create all arrays of non-negative integers of length N where the array sum is equal to T. The output order of arrays does not matter.

Possible solutions are e.g.

N = 5, T = 2:  
1 1 0 0 0  
1 0 1 0 0  
1 0 0 1 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 0 1 1 0
0 0 1 0 1
0 0 0 1 1
2 0 0 0 0  
0 2 0 0 0  
0 0 2 0 0  
0 0 0 2 0  
0 0 0 0 2
N = 4, T = 5  
0 4 1 0  
1 1 2 1  
2 0 3 0  
0 3 1 1  
... 

Erroneous outputs would be:

N = 3, T = 1  
1 1 1  
3 0 0  

N = 4, T = 2  
0 1 1
0 2 0 0 0 0

Edit: I sadly do not understand most of these very short code golf languages (but admire the creativity of them). To understand what you mean, main stream languages or explanations are encouraged. (How about Java, C# or C++?)

\$\endgroup\$
16
  • 1
    \$\begingroup\$ Welcome to Code Golf! This is a bit vague for a tips question. If you want the answers to be as short as possible, you can tag it with code-golf, which is what I'd recommend. \$\endgroup\$ – Redwolf Programs Mar 15 at 18:18
  • 1
    \$\begingroup\$ Thanks! Added the tag. \$\endgroup\$ – InfoMathze Mar 15 at 18:19
  • 2
    \$\begingroup\$ Welcome to Code Golf and nice first question! For future reference, we recommend using the Sandbox to get feedback on challenge ideas before posting them to main. This needs a bit more information to fully clarify it, namely what you mean by "array-sum", and changing the test cases into actual test cases rather than "working" and "not working" \$\endgroup\$ – caird coinheringaahing Mar 15 at 18:30
  • 5
    \$\begingroup\$ Also, regarding your most recent edit ("I sadly do not understand most of these very short code golf languages (but admire the creativity of them). To understand what you mean, main stream languages are encouraged"), I suggest encouraging explanations rather than "mainstream languages". Personally, I can understand a well explained Stax answer much better than a Python answer with no explanation \$\endgroup\$ – caird coinheringaahing Mar 15 at 20:18
  • 7
    \$\begingroup\$ While this does seem like a good code golf challenge (and I'm surprised we don't seem to have it already), I'm a bit put off by your trying to use this site to help write code for you, as is apparent from your closed SO question. This is not what this site is for. Be aware that answers here optimize only for brevity and not coding good practice or teaching value. Even the mainstream languages you ask for are unlikely to be used in a mainstream way. \$\endgroup\$ – xnor Mar 16 at 2:35

29 Answers 29

11
\$\begingroup\$

Jelly (fork), 5 bytes

ŻṗSƘ⁸

Can't Try it online! as this is a fork of Jelly with some newly added commands. Ƙ was added 3 days ago.

Essentially a shortened version of my other answer

How it works

ŻṗSƘ⁸ - Main link. Takes T on the left and N on the right
Ż     - Yield [0, 1, ..., T]
 ṗ    - N'th Cartesian power
    ⁸ - Yield T
   Ƙ  - Keep those for which the result of the following equals T:
  S   -   Sum
\$\endgroup\$
7
  • \$\begingroup\$ Can you please fill out the page with differences from Jelly? I'd like to try the fork. \$\endgroup\$ – xigoi Mar 15 at 20:09
  • 2
    \$\begingroup\$ @xigoi I'm currently messing around with any "last" adjustments I might want to make to some of the quicks that fail for monads, so that's slipped my mind. I'll start transferring my "changelog" document to the repo now, thanks for reminding me! \$\endgroup\$ – caird coinheringaahing Mar 15 at 20:11
  • 1
    \$\begingroup\$ @xigoi Filled out \$\endgroup\$ – caird coinheringaahing Mar 15 at 21:19
  • \$\begingroup\$ That's awesome! \$\endgroup\$ – xigoi Mar 16 at 9:24
  • 1
    \$\begingroup\$ @UselesssCat You are correct; in UTF-8 this is 11 bytes. However, Jelly uses a special code page to represent the bytes. The actual byte-codes here are D2 F2 53 94 88 (in hex), but the code page is used to make it more "readable" \$\endgroup\$ – caird coinheringaahing Mar 17 at 23:44
11
\$\begingroup\$

JavaScript (V8),  71 69  67 bytes

Saved 1 byte thanks to @l4m2

Expects (n, t) and prints all possible arrays.

f=(n,t,a=[],v=0)=>n?f(n-1,t,[...a,v])|t&&f(n,t-1,a,v+1):t||print(a)

Try it online!

Commented

f = (             // f is a recursive function taking:
  n,              //   n   = expected number of entries
  t,              //   t   = expected sum
  a = [],         //   a[] = current output array
  v = 0           //   v   = current value to be added to a[]
) =>              //
  n ?             // if there's at least one more entry to add:
    f(            //   do a first recursive call:
      n - 1,      //     decrement n
      t,          //     pass t unchanged
      [...a, v]   //     append v to a[]
    ) | t         //   end of recursive call; yield t
    &&            //   if the above is truthy ...
    f(            //   ... do a 2nd recursive call:
      n,          //     pass n unchanged
      t - 1,      //     decrement t
      a,          //     pass a[] unchanged
      v + 1       //     increment v
    )             //   end of recursive call
  :               // else:
    t || print(a) //   print a[] if t = 0
\$\endgroup\$
3
  • \$\begingroup\$ 68 \$\endgroup\$ – l4m2 Mar 16 at 1:55
  • \$\begingroup\$ 67: f=(n,t,a,v=0)=>n?v>t||f(n,t,a,v+1)|f(n-1,t-v,a?[a,v]:v):t||print(a) \$\endgroup\$ – tsh Mar 16 at 4:05
  • \$\begingroup\$ @tsh I believe that exactly n entries must be displayed. \$\endgroup\$ – Arnauld Mar 16 at 10:13
10
\$\begingroup\$

Haskell, 44 42 bytes

1#t=[[t]]
n#t=[t-x:y|x<-[0..t],y<-(n-1)#x]

Try it online!

Takes n and t as input, returns the list of all the arrays of non-negative integers of length n that sum to t.

The implementation relies on the following recursive idea: such an array can always be obtained as the concatenation of the first element \$\texttt{x}\in\{0,1,\ldots,\texttt{t}\}\$ and an array y of length \$\texttt{n}-1\$ with sum equal to \$\texttt{t}-\texttt{x}\$.

EDIT: because of syntactic restrictions, it's actually more efficient (in terms of bytes) to pick \$\texttt{t}-\texttt{x}\$ as the first element, and recurse on \$(\texttt{n}-1,\texttt{x})\$.

\$\endgroup\$
2
8
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

1~Table~#~FrobeniusSolve~#2&

Try it online!

FrobeniusSolve[     (* find all nonnegative integer vectors x s.t.: *)
 1~Table~#,         (*  {1,...(N 1s)...,1}.x *)
 #2]                (*  =T *)
\$\endgroup\$
8
\$\begingroup\$

Ruby, 56 53 bytes

->n,t{(a=*0..t).product(*[a]*~-n){|a|a.sum==t&&p(a)}}

Try it online!

Ironically, this is shorter than directly using a built-in method - that's the result of long names:

Ruby, 58 57 bytes

->n,t{[*0..t].repeated_permutation(n){|a|a.sum==t&&p(a)}}

Try it online!

Thanks to Dingus for -3 and -1 bytes, respectively.

\$\endgroup\$
0
7
\$\begingroup\$

J, 26 bytes

((=1&#.)#])]>@,@{@#<@i.@>:

Try it online!

Similar to the other answers, this just generates all possible Cartesian products and filters them.

\$\endgroup\$
7
\$\begingroup\$

Haskell, 46 42 bytes

n#t=[x|x<-mapM(\u->[0..t])[1..n],sum x==t]

Try it online!

  • saved 4 thanks to @Delfad0r
\$\endgroup\$
0
6
\$\begingroup\$

C++ (gcc), 164 \$\cdots\$ 153 151 bytes

Saved 3 bytes thanks to ceilingcat!!!
Added 7 bytes to fix a bug kindly pointed out by Neil.
Saved 2 bytes thanks to Neil!!!

#import<bits/stdc++.h>
auto f(int n, int t){std::vector<int>r;for(int i=pow(++t,n),v,j;i--;v||(r.push_back(i),0))for(v=t-1,j=i;j;j/=t)v-=j%t;return r;}

Try it online!

You asked for a C++ answer so here's one! :D

Inputs positive integers \$n\$ and \$t\$ and returns a std::vector holding all of the \$n\$-digit base\$_{t+1}\$ integers who's \$n\$ base\$_{t+1}\$ digits all sum to \$t\$.

\$\endgroup\$
4
  • \$\begingroup\$ Isn't this limited to values of T up to 9? \$\endgroup\$ – Neil Mar 16 at 10:47
  • \$\begingroup\$ @Neil Yes, you're right, Fixed - thanks! :D \$\endgroup\$ – Noodle9 Mar 16 at 13:21
  • \$\begingroup\$ Would it save bytes to start i at pow(t+1,n) and then i-- in the loop? \$\endgroup\$ – Neil Mar 16 at 13:46
  • \$\begingroup\$ @Neil Nice one - thanks! :D \$\endgroup\$ – Noodle9 Mar 16 at 13:49
5
\$\begingroup\$

Zsh, 86 bytes

for p (`eval echo ${(l:$2*8::{0..$1},:)}`)(for a (${(s:,:)p})let t+=a;let t-$1||<<<$p)

Try it online!

  • ${(l:$2*8::{0..$1},:)}: repeat the string "{0..$1}", \$ n \$ ($2) times
  • eval: expand the string {0..$1},{0..$1},{0..$1},, which produces the \$ n\$-permutations of the range \$ 0, 1, 2, ... T \$
  • `echo`: print those permutations, space-separated
  • for p (): for each permutation, $p:
    • (): subshell, which ensures $t is reset to \$ 0 \$ each iteration
    • ${(s:,:)p}: split the permutation $p on commas
    • for a (): for each item $a in the permutation:
      • let t+=a: increment $t by $a
      • (this sums the permutation into $t)
    • let t-$1: find the difference between $t and \$ T \$ ($1)
      • ||: if that is zero:
        • <<<$p: print $p
\$\endgroup\$
5
\$\begingroup\$

APL (Dyalog Extended), 10 bytes

∪↑¯⍸¨,⍳⎕⍴⎕

Try it online!

Filtering is not so convenient in APL, so here is a solution that uses each input only once. A full program, which takes N then K from stdin, and prints a matrix. The final can be omitted if duplicate rows are allowed.

How it works

∪↑¯⍸¨,⍳⎕⍴⎕  ⍝ First input (right): N, Second input (left): T
       ⎕⍴⎕  ⍝ T copies of N
     ,⍳     ⍝ Cartesian product of T copies of 1..N
  ¯⍸¨       ⍝ For each vector V from above,
            ⍝ creates another vector W where each index i appears W[i] times in V
            ⍝ e.g. [3 3 4] → [0 0 2 1]
 ↑          ⍝ Mix (promote a vector of vectors to a matrix), padding with zeros
∪           ⍝ Take unique rows
\$\endgroup\$
4
\$\begingroup\$

R, 62 bytes

function(n,t)(m=expand.grid(rep(list(0:t),n)))[rowSums(m)==t,]

Try it online!

Slightly shorter (and more efficient) to use expand.grid rather than combn.

Generates the cartesian product of [0..t] with itself n times, then filters for those with row sums equal to t.

R, 63 bytes

function(n,t)(m=unique(t(combn(rep(0:t,n),n))))[rowSums(m)==t,]

Try it online!

\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 16 bytes

{(y=+/)#+!x#1+y}

Try it online!

{(y=+/)#+!x#1+y} / a function with arguments x (N) and y (T)
           #     / create a list
          x      / of x copies
            1+y  / of 1+y 
         !       / make an odometer from this list (ranged permutations)
        +        / transpose the result
       #         / keep only those lists
 (  +/)          / that have sum which
  y=             / equals y 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Using odometer for this is nice. \$\endgroup\$ – Jonah Mar 16 at 17:14
  • \$\begingroup\$ @Jonah Yes, it's good that K has it built-in \$\endgroup\$ – Galen Ivanov Mar 16 at 18:22
3
\$\begingroup\$

Python 3, 87 bytes

lambda n,t:[k for k in product(range(t+1),repeat=n)if sum(k)==t]
from itertools import*

Try it online!

Explanation

First use range to get all integers between 0and t and use itertools.product to find the array of cartesian product of itself repeated n times (so that would include all arrays of length n where each element is between 0 and t). Among all such arrays, we only pick the ones with sum equal to t.

\$\endgroup\$
4
  • \$\begingroup\$ Also working. But as in the other answer, I do not understand why. \$\endgroup\$ – InfoMathze Mar 15 at 18:41
  • \$\begingroup\$ Cool, thanks for adding explanation. \$\endgroup\$ – InfoMathze Mar 15 at 18:47
  • \$\begingroup\$ I'm a Python programmer but I don't get why this works when you put the import line below the lambda? Can you add more explanation? \$\endgroup\$ – smci Mar 17 at 7:32
  • \$\begingroup\$ @smci It's a function, and the function is called in the footer, so itertools has already been imported and the function runs after the import. \$\endgroup\$ – Manish Kundu Mar 17 at 7:45
3
\$\begingroup\$

Jelly, 7 bytes

ŻṗS=¥Ƈ⁸

Try it online!

How it works

ŻṗS=¥Ƈ⁸ - Main link. Takes T on the left and N on the right
Ż       - Yield [0, 1, ..., T]
 ṗ      - N'th Cartesian power
    ¥Ƈ  - Keep those for while the following is true:
  S     -   Sum
   =  ⁸ -   Equals T
\$\endgroup\$
3
\$\begingroup\$

Japt, 20 bytes

pVÄ osU ù'0 m¬f_x ¥V

Try it

Input : U = n , V = t

    o    - numbers from 0 to..
pVÄ      - (n raised to t+1)excluded
     sU  - to base n

ù'0      - pad to left with '0' to max length element
m¬       - split each 
f_       - keep
  x ¥V   - sum == t
\$\endgroup\$
2
  • \$\begingroup\$ I think you can save a byte by moving the ¬ inside f instead of a separate step: pVÄ osU ù'0 f_¬x ¥V \$\endgroup\$ – Kamil Drakari Mar 17 at 2:07
  • \$\begingroup\$ @Kamil Drakari yes but it will print numbers joined.. Your suggestion make me realize that my answer is not valid.. It works only for t < 10 e.g. single digits. \$\endgroup\$ – AZTECCO Mar 17 at 10:00
3
\$\begingroup\$

Charcoal, 36 bytes

Nθ⊞υ⟦N⟧Fυ¿⁼Lιθ⟦⪫ι,⟧«≔⊟ιηF⊕η⊞υ⁺ι⟦κ⁻ηκ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input N.

⊞υ⟦N⟧Fυ

Start a breadth first search with an array [T].

¿⁼Lιθ

If the current array has the correct number of entries, ...

⟦⪫ι,⟧

... then join it with commas and print it on its own line, ...

«

... otherwise:

≔⊟ιη

Remove the last entry from the array.

F⊕η

For all values from 0 to that entry inclusive...

⊞υ⁺ι⟦κ⁻ηκ

... concatenate the value and the difference from the original last entry to the remainder of the array, and save that for a future search pass.

\$\endgroup\$
3
\$\begingroup\$

MATL, 13 bytes

Q:qZ^t!s1G=Y)

First input is T and second input is N

Try it out at MATL Online

Explanation

        % Implicitly grab the first input, T
Q:q     % Add 1 to T, create array from 1...(T+1), subtract 1 to yield 0...T
Z^      % Perform the Cartesian product with the second input
t       % Duplicate the result
!s      % Sum across the rows
1G      % Explicitly grab the first input again, T
=       % Compare the sum of each row to T
Y)      % Use this a logical index to grab only those rows where the sum == T
        % Implicitly display the result
\$\endgroup\$
3
\$\begingroup\$

Retina, 50 bytes

G`$
.+
*
"$+"+%Lv$`_*$
$`,$&
(_*),
$.1,
Lm$`,$
$%`

Try it online! No test suite because this program uses history. Explanation:

G`$

Delete N. (Don't worry, we can get it back later via $+.)

.+
*

Convert T to unary.

"$+"+`

Repeat N times...

%`

... for each line...

Lv$`_*$

... for all the suffixes of the last entry, i.e. the numbers from it down to zero...

$`,$&

... split the last entry into two values that sum to it.

(_*),
$.1,

Convert all the values to decimal, except for the last value on each line.

Lm$`,$
$%`

List only those lines that end with a zero entry, keeping only the prefix of the line. This is required because we split T N times, resulting in a list of length N+1, so to fix this we only keep those entries that end with zero, dropping that zero from the final output.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

ݹãʒOQ

Try it online!

ݹãʒOQ  # full program
   ʒ    # all elements of...
  ã     # all combinations of...
Ý       # [0, 1, 2, ...,
        # ..., implicit input...
Ý       # ]...
  ã     # repeated...
 ¹      # first input...
  ã     # times...
   ʒ    # where...
    O   # sum of all elements in...
        # (implicit) current element in list...
     Q  # is equal to...
        # implicit input
        # implicit output
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 40 bytes

Select[Range[0,s=#2]~Tuples~#,Tr@#==s&]&

Try it online!

-2 bytes from @att

\$\endgroup\$
5
  • \$\begingroup\$ Sorry, i was not specific enough in my original question. \$\endgroup\$ – InfoMathze Mar 15 at 18:30
  • \$\begingroup\$ @InfoMathze is my updated answer correct? \$\endgroup\$ – ZaMoC Mar 15 at 18:31
  • \$\begingroup\$ I guess. Very cool. But i am not firm enough in Mathematica to understand why. :D \$\endgroup\$ – InfoMathze Mar 15 at 18:33
  • \$\begingroup\$ Tuples's second argument doesn't need to be a list \$\endgroup\$ – att Mar 15 at 21:04
  • \$\begingroup\$ @att fixed!..... \$\endgroup\$ – ZaMoC Mar 15 at 22:12
2
\$\begingroup\$

Functional Bash*, 160 bytes

* This is bash with the additional constraint that you can't mutate variables.

d=$(eval echo $(printf "{0..$1}%.0s+" $(seq $1))|tr \  \\n)
paste <(sed s/$/0/<<<$d|bc|awk "{print match(\$0,/^$2$/)?1:0}") <(sed s/+/\ /g<<<$d)|grep ^1|cut -f2

Try it online!

Could be golfed more, but sort of a fun idea.

\$\endgroup\$
2
\$\begingroup\$

Japt, 17 bytes

ÆVòÃc àU f_x ¥VÃâ

Try it online!

Uses a significantly different strategy from the other Japt answer. The order of the outputs is weird, but all of them seem to be there.

Explanation:

ÆVòÃc àU f_x ¥VÃâ    
 Vò                  # Create the array [0...T]
Æ  Ã                 # Create N copies of that array
    c                # Flatten them all into a single array
      àU             # Create all combinations of elements of that array that have length N
         f_    Ã     # Keep only the ones where:
           x         #  The sum of the numbers
             ¥V      #  Is equal to T
                â    # Remove any duplicates
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 60 bytes

f=(n,t,a,g=i=>f(n,t-i,[a,i])|i&&g(i-1))=>--n?g(t):print(t+a)

Try it online!

f=(n,t,
  a, // previous numbers, initialed as undefined (empty)
  g= // helper function to loop current number from t to 0
    i=> // `i` is current number
      f(n,t-i,[a,i])| // try to use current number and `t-i` remined
      i&&g(i-1) // loop until i = 0
)=>
  --n? // Is more than 1 number required?
    g(t): // Try current number, loop from `t`
    print(t+a) // We found an partition with t and previous numbers
\$\endgroup\$
2
\$\begingroup\$

C (clang), 133 124 bytes

p,i,j,r;f(n,t){for(p=++t,j=n;--j;p*=t);for(;i=j=--p;){for(r=t-1;j;j/=t)r-=j%t;for(j=n;j--;i/=t)r||printf("%d%c",i%t,9+!j);}}

Try it online!

  • iterates over all numbers up to (t+1)^n , convert to base t+1 then prints only if digits sums to t.
  • prints elements separated by tab.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Your code is correctly iterating over all numbers up to (t+1)ⁿ, not tⁿ as your explanation claims. \$\endgroup\$ – Neil Mar 16 at 10:50
  • \$\begingroup\$ If it helps, you can use s(n,t){return n<2?1:t?s(n-1,t)+s(n,t-1):1;} for the size of the returned array (in case you don't want to print) \$\endgroup\$ – user Mar 16 at 13:20
  • 1
    \$\begingroup\$ To print or not to print?.. The C dilemma! Thanks for the tip @user but I don't know if it can help to return instead of printing.. Since it would be a slightly different approach it could be a different answer \$\endgroup\$ – AZTECCO Mar 16 at 13:51
  • \$\begingroup\$ Oh ok. I'm not a C person so I was hoping someone else would know how to use it :) \$\endgroup\$ – user Mar 16 at 14:07
  • 1
    \$\begingroup\$ @user Just thinking a little, the problem I can spot with the approach you suggested is that you have to pay also malloc call to allocate memory.. A lot of bytes I think.. Usually it's better to just print in C \$\endgroup\$ – AZTECCO Mar 16 at 14:22
1
\$\begingroup\$

Python 3, 74 bytes

f=lambda N,T:N and[j+[i]for i in range(T+1)for j in f(N-1,T-i)]or[[]]*-~-T

Try it online!

Shortened version of this

def f(N,T):
  if N == 0:
    if T == 0: return [[]]
    else: return []
  else:
    l = []
    for i in range(T+1):   # possible last elements
      for j in f(N-1,T-i): # solutions for rest of elements
        l.append(j+[i])
    return l
\$\endgroup\$
1
\$\begingroup\$

JavaScript (V8), 76 74 bytes

f=(n,t,z=t)=>n<2?[[t]]:f(n-1,t-z).map(a=>[z,...a]).concat(z?f(n,t,z-1):[])

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 74: f=(n,t,z=t)=>n<2?[[t]]:f(n-1,t-z).map(a=>[z,...a]).concat(z?f(n,t,z-1):[]) \$\endgroup\$ – tsh Mar 17 at 1:46
  • \$\begingroup\$ @tsh Thanks, I didn't think of that! \$\endgroup\$ – user Mar 17 at 20:55
1
\$\begingroup\$

Haskell 73 (88) bytes

This solution is longer than both existing Haskell solutions. But it's fun, and that's what code golf is about.

1#t=[[t]]
n#1=(n-1)#1>>=(\p->[0:p,1:(0<$p)])
n#t=zipWith(+)<$>n#1<*>n#(t-1)

Here's how it works:

  • Bottom case: If, given any particular N, you could solve the problem for T=1 and any other Ta, you could solve it for Ta+1 as well. You would only have to find every possible pairing of a Ta array and a T=1 array and add up both arrays element-wise. So by induction if you could solve the problem for T=1, you could solve it for any T.
  • Middle case: Now you only have an infinite number of problems remaining: solving the task for any N, given T=1. But if you had a solution for T=1 and any Na, you could get a solution for T=1 and Na+1 by simply putting a zero in front of every existing array and adding one more trivial array (in this case, many times). So actually you only have to solve the task for T=1 and N=1.
  • Top case: Now that's trivial.

To get down to this enormous reduction of being almost longer than all existing Haskell solutions combined, this solution not only uses almost every trick in my book, but it also exploits two holes of the task description:

  1. The task doesn't state that an array can only appear once
  2. No restrictions are given for N and T, so I didn't make it work for non-trivial T=0.

To get rid of both exploits, more bytes are necessary. But yet another level of beauty emerges, both because the solution is now actually longer than all existing Haskell solutions combined, and because the middle case gains some symmetry.

1#t=[[t]]
n#0=[0<$[1..n]]
(n+1)#1=[1:p|p<-n#0]++[0:p|p<-n#1]
n#(t+1)=zipWith(+)<$>n#1<*>n#t
\$\endgroup\$
0
\$\begingroup\$

Ruby, 54 53 bytes

f=->n,t,*a{n>1?0.upto(t){|x|f[n-1,t-x,*a,x]}:p(a<<t)}

Try it online!

I don't know if the initial "f=" is considered part of the function. If I could move that to the header, this would be 51 bytes. I've always considered it a part of the function (because of recursion), but I think I've seen answers where it was removed.

\$\endgroup\$
0
\$\begingroup\$

Macaulay2, 36 bytes

n->t->exponents(sum gens(ZZ[n:x]))^t

Try it online!

This is based on the fact that, by the multinomial theorem, the multivariate polynomial $$(x_1 + \cdots + x_n)^t = \sum_{t_1+\cdots+t_n=t} \binom{t}{t_1,\dots,t_n} x_1^{t_1} \cdots x_n^{t_n} \in ℤ[x_1,\dots,x_n]$$ involves all the monomials of degree t in n variables when fully expanded. As the exponents of each monomial sum to t, taking all the exponent vectors of this polynomial gives the solution.

For example, with n=2, t=4, the polynomial $$(x_1 + x_2)^4 = x_1^4 + 4 x_1^3 x_2 + 6 x_1^2 x_2^2 + 4 x_1 x_2^3 + x_2^4$$ has exponents (4,0), (3,1), (2,2), (1,3), (0,4).


Edit: As a side note, there is even a builtin for this: compositions (12 bytes). Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.