Brachylog (v2), 15 bytes (random) or 13 bytes (all possibilities)

Random

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Try it online!

Function submission (seen in TIO with a wrapper making it into a full program).

Explanation

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

~l               Specify a property of a list: its length is equal to the input,

    ᵐ              and it is composed entirely of

  ℕ₁                 integers ≥ 1,

       √           for which the square root of the

      +              sum of the list

        ?              is the input.

     A   ∧A      Restricting yourself to lists with that property,

           ≜₁      pick random possible values

             ᵐ       for each element in turn,

              ≠    until you find one whose elements are all distinct.

All possibilities

~lℕ₁ᵐ<₁.+√?∧≜

Try it online!

Function submission, which generates all possible outputs.

Explanation

~lℕ₁ᵐ<₁.+√?∧≜

~l               Specify a property of a list: its length is equal to the input,

    ᵐ              it is composed entirely of

  ℕ₁                 integers ≥ 1,

     <₁            it is strictly increasing,

         √         and the square root of the

        +            sum of the list

          ?            is the input.

       .   ∧≜    Generate all specific lists with that property.

I'm fairly surprised that ∧≜ works (you'd normally have to write ∧~≜ in order to brute-force the output rather than the input), but it turns out that ≜ has an input=output assumption so it doesn't matter which way round you run it.

Bonus task

In order to get some insight into the sequence of the number of possibilities, I created a different TIO wrapper which runs the program on successive integers to give the sequence of output counts:

1,1,3,9,30,110,436,1801,7657,33401

A trip to OEIS discovers that this is already a known sequence, A107379, described pretty much as in the question (apparently you get the same sequence if you restrict it to odd numbers). The page lists several formulas for the sequence (although none is particularly simple; the second looks like a direct formula for the value but I don't understand the notation).

05AB1E, 11 bytes

nÅœʒDÙQ}sùΩ

Try it online or verify all test cases.

Explanation:

n             # Take the square of the (implicit) input

              #  i.e. 3 → 9

 Ŝ           # Get all integer-lists using integers in the range [1, val) that sum to val

              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]

   ʒ   }      # Filter the list to only keep lists with unique values:

    D         # Duplicate the current value

     Ù        # Uniquify it

              #  i.e. [2,2,5] → [2,5]

      Q       # Check if it's still the same

              #  i.e. [2,2,5] and [2,5] → 0 (falsey)

        s     # Swap to take the (implicit) input again

         ù    # Only leave lists of that size

              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3

              #   → [[1,2,6],[1,3,5],[2,3,4]]

          Ω   # Pick a random list from the list of lists (and output implicitly)

Python (2 or 3), 85 bytes

def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)

from random import*

Try it online!

R, 68, 75 48 bytes (random) and 70 bytes (deterministic)

@Giuseppe's rejection sampling method:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Try it online!

Golfed original:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Try it online!

The *!!1:2 business is to avoid the odd way sample act when the first argument has length 1.

Jelly, 9 bytes

²œcS=¥Ƈ²X

Try it online!

Generate all n-combinations of the list [1..n²], filter to keep those with sum n², then pick a random one.

Java 10, 250 242 222 bytes

import java.util.*;n->{for(;;){int i=n+1,r=new int[i],d=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-20 bytes thanks to @nwellnhof.

Watch out, Java coming through.. It's 'only' five times as long as the other four answers combined, so not too bad I guess.. rofl.

It does run n=1 through n=25 (combined) in less than 2 seconds though, so I'll probably post a modified version to the speed version of this challenge (that's currently still in the Sandbox) as well.

Try it online.

Explanation:

In pseudo-code we do the following:

1) Generate an array of size n+1 containing: 0, n squared, and n-1 amount of random integers in the range [0, n squared)

2) Sort this array

3) Create a second array of size n containing the forward differences of pairs

These first three steps will give us an array containing n random integers (in the range [0, n squared) that sum to n squared.

4a) If not all random values are unique, or any of them is 0: try again from step 1

4b) Else: return this differences array as result

As for the actual code:

import java.util.*;      // Required import for HashSet and Arrays

n->{                     // Method with int parameter and Set return-type

  for(;;){               //  Loop indefinitely

    int i=n+1,           //   Set `i` to `n+1`

        r=new int[i];  //   Create an array of size `n+1`

    var S=new HashSet(); //   Result-set, starting empty

    for(r[n<2?           //   If `n` is 1:

           0             //    Set the first item in the first array to:

          :              //   Else:

           1]            //    Set the second item in the first array to:

             =n*n;       //   `n` squared

        i-->2;)          //   Loop `i` in the range [`n`, 2]:

      r[i]=              //    Set the `i`'th value in the first array to:

           (int)(Math.random()*n*n); 

                         //     A random value in the range [0, `n` squared)

    for(Arrays.sort(r),  //   Sort the first array

        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:

      S.add(             //    Add to the Set:

        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array

    if(!S.contains(0)    //   If the Set does not contain a 0

       &S.size()==n)     //   and its size is equal to `n`:

      return S;}}        //    Return this Set as the result

                         //   (Implicit else: continue the infinite loop)

Perl 6, 41 bytes

{first *.sum==$_²,(1..$_²).pick($_)xx*}

Try it online!

• 
  (1 .. $_²) is the range of numbers from 1 to the square of the input number


• 
  .pick($_) randomly chooses a distinct subset of that range


• 
  xx * replicates the preceding expression infinitely


• 
  first *.sum == $_² selects the first of those number sets that sums to the square of the input number

Pyth, 13 12 bytes

Ofq*QQsT.cS*

Try it online here. Note that the online interpreter runs into a MemoryError for inputs greater than 5.

Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())

                 Trailing QQQ inferred

          S*QQQ   [1-Q*Q]

        .c    Q   All combinations of the above of length Q, without repeats

 f                Keep elements of the above, as T, where the following is truthy:

      sT            Is the sum of T...

  q                 ... equal to...

   *QQ              ... Q*Q?

O                 Choose a random element of those remaining sets, implicit print

Edit: saved a byte by taking an alternative approach. Previous version: Of&qQlT{IT./*

Python 3, 136 134 127 121 114 bytes

from random import*

def f(n):

	s={randint(1,n*n)for _ in range(n)}

	return len(s)==n and sum(s)==n*n and s or f(n)

Try it online!

A commenter corrected me, and this now hits recursion max depth at f(5) instead of f(1). Much closer to being a real competing answer.

I've seen it do f(5) once, and I'm working on trying to implement this with shuffle.

I tried making some lambda expressions for s=..., but that didn't help on bytes. Maybe someone else can do something with this:
s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Thanks to Kevin for shaving off another 7 bytes.

APL (Dyalog Unicode), 20 bytes^SBCS

Anonymous prefix lambda.

{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Try it online!

{…} "dfn"; ⍵ is argument

 ⍵*2 square the argument

 s← assign to s (for square)

 ⍵? find n random indices from 1…s without replacement

 c← assign to c (for candidate)

 +/ sum them

 s= compare to s

 : if equal

  c return the candidate

 ⋄ else

  ∇⍵ recurse on the argument

APL (Dyalog Classic), 18 bytes

(≢?≢×≢)⍣(0=+.-∘≢)⍳

Try it online!

uses ⎕io←1

⍳ generates the numbers 1 2 ... n

(...)⍣(...) keep applying the function on the left until the function on the right returns true

≢ length, i.e. n

≢?≢×≢ choose randomly n distinct integers between 1 and n²

+.-∘≢ subtract the length from each number and sum

0= if the sum is 0, stop looping, otherwise try again

MATL, 18 13 bytes

`xGU:GZrtsGU-

Try it online!

`	# do..while:

x	# delete from stack. This implicitly reads input the first time

	# and removes it. It also deletes the previous invalid answer.

GU:	# paste input and push [1...n^2]

GZr	# select a single combination of n elements from [1..n^2]

tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top

Japt, 12 bytes

²õ àU ö@²¥Xx

Try it

                 :Implicit input of integer U

²                :U squared

 õ               :Range [1,U²]

   àU            :Combinations of length U

      ö@         :Return a random element that returns true when passed through the following function as X

        ²        :  U squared

         ¥       :  Equals

          Xx     :  X reduced by addition

Java (JDK), 127 bytes

n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

Try it online!

Infinite loop until a set with the criteria matches.

I hope you have the time, because it's very sloooooow! It can't even go to 10 without timing out.

Batch, 182 145 bytes

@set/an=%1,r=n*n,l=r+1

@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Explanation: Calculates the minimum and maximum allowable pick, given that the numbers are to be picked in descending order, and chooses a random value within the range. Example for an input of 4:

• We start with 16 left. We can't pick 11 or more because the remaining 3 picks must add to at least 6. We also need to pick at least 6, because if we only pick 5, the remaining 3 picks can only add to 9, which isn't enough for 16. We pick a random value from 6 to 10, say 6.


• We have 10 left. We can't pick 8 or more because the remaining 2 picks must add to at least 3. As it happens, we can't pick 6 or more because we picked 6 last time. We also need to pick at least 5, because if we only pick 4, the remaining 2 picks can only add to 5, for a grand total of 15. We pick a random value from 5 to 5, say 5 (!).


• We have 5 left. We can't pick 5 or more because the remaining pick must add to at least 1, and also because we picked 5 last time. We also need to pick at least 3, because if we only pick 2, the remaining pick can only be 1, for a grand total of 14. We pick a random value from 3 to 4, say 4.


• We have 1 left. As it turns out, the algorithm chooses a range of 1 to 1, and we pick 1 as the final number.

JavaScript, 647 291 261 260 259 251 239 bytes

Thanks to @Veskah for -10 bytes at original version and "Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned"

(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Try it online!

Create an array of n^2 1-based indexes, sort array randomly, slice n elements from array. While the sum of the random elements does not equal n^2 loop array of random elements; if sum of array elements is greater than n^2 and current element -1 does not equal zero or current element -1 is not in current array, subtract 1; if sum of array is less than n^2 and current element +1 is not in array, add 1 to element. If array sum is equal to n^2 break loop, output array.

Japt, 20 bytes

²õ ö¬oU íUõ+)Õæ@²¥Xx

Try it online!

Extremely heavily takes advantage of "Non-uniform" randomness, almost always outputs the first n odd numbers, which happens to sum to n^2. In theory it can output any other valid set, though I've only been able to confirm that for small n.

Explanation:

²õ                      :Generate the range [1...n^2]

   ö¬                   :Order it randomly

     oU                 :Get the last n items

        í   )Õ          :Put it in an array with...

         Uõ+            : The first n odd numbers

              æ_        :Get the first one where...

                  Xx    : The sum

                ²¥      : equals n^2

Ruby, 46 bytes

->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Try it online!

C (gcc), 128 125 bytes

p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Try it online!

-3 bytes thanks to ceilingcat

NOTE: The probability is very very far from uniform. See explanation for what I mean and a better means to test that it works (by making the distribution closer to uniform [but still a far cry from it]).

How?

The basic idea is to only choose increasing numbers so as to not worry about duplicates. Whenever we pick a number we have a non-zero chance of 'skipping' it if allowable.

To decide if we can skip a number we need to know x the total left to be reached, k the number of elements we still have to use, and y the current candidate value. The smallest possible number that we could still pick would consist of $$y+(y+1)+(y+2)+...$$ added to the current value. In particular we require the above expression to be less than x. The formula will be $$frac{k(k+1)}{2}+k(y+1)+y<x$$ Unfortunately we have to be a bit careful about rearranging this formula due to integer truncation in C, so I couldn't really find a way to golf it.

Nonetheless the logic is to have a chance to discard any y that satisfies the above equation.

The code

p(_){printf("%d ",_);}  // Define print(int)

f(n,x,y,i){             // Define f(n,...) as the function we want

    x=n*n;              // Set x to n^2

    y=1;                // Set y to 1

    for(i=0;++i<n;){    // n-1 times do...

        while(rand()&&  // While rand() is non-zero [very very likely] AND

            (n-i)*      // (n-i) is the 'k' in the formula

            (n-i+1)/2+  // This first half takes care of the increment

            (n-i)*(y+1) // This second half takes care of the y+1 starting point

            +y<x)       // The +y takes care of the current value of y

        y++;            // If rand() returned non-zero and we can skip y, do so

    p(y);               // Print y

    x-=y++;             // Subtract y from the total and increment it

    }p(x);}             // Print what's left over.

The trick I mentioned to better test the code involves replacing rand()&& with rand()%2&& so that there is a 50-50 chance that any given y is skipped, rather than a 1 in RAND_MAX chance that any given y is used.

Clean, 172 bytes

import StdEnv,Math.Random,Data.List

? ::!Int->Int

?_=code{

ccall time "I:I"

}

$n=find(s=length s==n&&sum s==n^2)(subsequences(nub(map(inc oe=e rem n^2)(genRandInt(?0)))))

Try it online!

Python (2 or 3), 84 bytes

from random import*;l=lambda n,s=:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Try it online!

Hits max recursion depth at around l(5)

Kotlin, 32 bytes

{(1..it*it).shuffled().take(it)}

Try it online!

Mathematica 40 bytes

RandomChoice[IntegerPartitions[n^2, {n}]]

Wolfram Language (Mathematica), 49 bytes

(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Try it online!

Golfed version by @J42161217.

Wolfram Language (Mathematica), 62 bytes

Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Try it online!

How it works

Mainly based on this Math.SE question. In order to get partitions of $n^2$ into $n$ distinct parts, get partitions of $n^2 - (n^2-n)/2 = (n^2+n)/2$ instead and add $0 cdots n-1$ to each element. Since Mathematica gives the partitions in decreasing order, $n-1 cdots 0$ is added instead.

The answer to the Bonus Task

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

Yes. Define $part(n,k)$ as the number of partitions of $n$ into exactly $k$ parts. Then it satisfies the following recurrence relation:

$$ part(n,k) = part(n-1,k-1) + part(n-k,k) $$

You can understand it as "If a partition contains a 1, remove it; otherwise, subtract 1 from every term". More explanation here on another Math.SE question. Combined with the initial conditions $ part(n,1) = 1 $ and $ n < k Rightarrow part(n,k) = 0 $, you can compute it with a program. The desired answer will be:

$$ part(frac{n^2+n}{2}, n) $$

which is, in Mathematica:

Length@IntegerPartitions[#*(#+1)/2,{#}]&

Try it online!