[Question]
  [
Randomness is fun. Challenges with no point are fun.
Write a function that, given integer input `n`, will output a **set** (unordered, unique) of exactly `n` random integers between `1` and `n^2` (inclusive) such that the sum of all integers is equal to `n^2`.
Randomness does *not* have to be uniform, provided each valid set has a non-zero chance to occur.
Shortest answer in bytes (per each language) wins.
## Examples
```
Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1
Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3
Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2
Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4
Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8
Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1
```
**Bonus Task:** Is there a formula to calculate the number of valid permutations for a given `n`?
  
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog) (v2), 15 bytes (random) or 13 bytes (all possibilities)
## Random
```
~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r/vy7nUcvUR02ND7dOcNR@1DHL/lHHcsdHnXMgQo86F/z/b/w/CgA "Brachylog – 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!](https://tio.run/##SypKTM6ozMlPN/r/qG3Do6bGh1vb/9flPGqZCmZPsAFSetqPOmbZP@pY/qhzzv//xv@jAA "Brachylog – Try It Online")
Function submission, which [generates](https://codegolf.meta.stackexchange.com/a/10753/76359) 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](https://tio.run/##SypKTM6ozMlPN/r/aP6yR02N1Y/aNjxqanq4bU7tw60T/tflPGqZChQGsm2AlJ72o45Z9o86lj/qnPP/v6HB/ygA) 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](http://oeis.org/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).
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 11 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
nÅœʒDÙQ}sùΩ
```
[Try it online](https://tio.run/##ARwA4/9vc2FiaWX//27DhcWTypJEw5lRfXPDuc6p//82) or [verify all test cases](https://tio.run/##ASoA1f9vc2FiaWX/N0dOPyIg4oaSICI/TkT/bsOFxZPKkkTDmVF9c8O5zqn/LP8).
**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)
```
[Answer]
# [Python](https://docs.python.org/) (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!](https://tio.run/##NY2xDsIwDERn@hXeGpeAKANDUfmXiiYQiTiR7Q79@pAWYcmy7k73nFd9J7qWEHNiBVmlqXsWp@yeC0tI9AkxqOkv22CZnQdvCAceZYr54wxP9HKmt9TRsUdLeGenC5OpxjjKEg0jdgyJ92LjOUWopbme39uu@BqqE4VA8OfBDYfmkDmQ7pmF9vRobYVsCssX "Python 2 – Try It Online")**
[Answer]
# [R](https://www.r-project.org/), ~~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!](https://tio.run/##K/qfZvs/rTQvuSQzP08jT7O6PCMzJ1WjuDRXw01T0TYvzkjTzbY4MbcAKAjk6ORpWrvV/k/TMNTkStMwAhHGIMIERJiCCDMQYa75HwA "R – 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!](https://tio.run/##Fcq9DkAwEADg3VOw3UkNrZ9B9CmMQkKjIXFXUeLxS5dv@q5g064I9mFz746BBWnjaGGQLU9KMCINws90Hiu82242MO7oH/JAqPVfMM8y2SohcQwWJCYWVKSMVJE60mD4AA "R – Try It Online")
The `*!!1:2` business is to avoid the odd way `sample` act when the first argument has length 1.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 bytes
```
²œcS=¥Ƈ²X
```
[Try it online!](https://tio.run/##y0rNyan8///QpqOTk4NtDy091n5oU8T///@NAQ "Jelly – Try It Online")
Generate all n-combinations of the list [1..n²], filter to keep those with sum n², then pick a random one.
[Answer]
# 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.](https://tio.run/##LVDBUsIwEL3zFSsHJ6E2UGY8aKyONy@iMz0yPYQ2SLBsmWSLg0yvfoCf6I/gBsghO/uy723eW5udSdf159Fttq0nWHOvOnKNGmkAGI/h3TDcLoFWFhZ7smnVdkggkuxODqrGhACvxuFhAOCQrF@aysIstgCFJagEw4BSM9IP@ApkyFUwA4Qcjpg@HpatF1rLQxx0OSbZjZ@XOdqvqDh3pd4ZD8UJeDFhxapC6kjyc3yYPk3uM54eoXZp@jjVnhl5XCrFq6GV8gbrdiPkiEfkmffsvdkHFdix8PKGd564Ey0LZeqadV2SlWlUktotxVWhqhaJbQYxkdeFCu7bCpnnKL2lziMUuu@POtrbdouG7V1c7lpXw4aJoiDv8GNegpHncOJHzo4zDe4hn95ySZLLK8DbYm0rAm9D1xBHhYqjPMUYz6UU@0B2o9qO1Jb1qUHhkiH8/fzCMDkzLpT@lH9//Ac)
**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)
```
[Answer]
# [Perl 6](http://perl6.org/), 41 bytes
```
{first *.sum==$_²,(1..$_²).pick($_)xx*}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/Oi2zqLhEQUuvuDTX1lYl/tAmHQ1DPT0QQ1OvIDM5W0MlXrOiQqv2f3FipYaSSryCrZ1CdZqCSnytkqZCRQWQoZCWX6QA1GP6HwA "Perl 6 – 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
[Answer]
# Pyth, ~~13~~ 12 bytes
```
Ofq*QQsT.cS*
```
Try it online [here](https://pyth.herokuapp.com/?code=Ofq%2AQQsT.cS%2A&input=3&debug=0). 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./*`
[Answer]
# [Python 3](https://docs.python.org/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!](https://tio.run/##RY1BCgMhDEXX4ymyGxUXle4GPEspjLaBGiU6i1J6dmtooavwyX/v12e/FzqPkbhk4Cvt82CuhbtVe0yQNJlNLS285InUtXdkyaTCcAEkYW5xlt5q4dgPJnhE0s2EQDAJaEf@JvvLMEmxDlHgX@GdP8lUZVlBt26rm0U0ZnwA "Python 3 – 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.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 20 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?")[SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set")
Anonymous prefix lambda.
```
{s=+/c←⍵?s←⍵*2:c⋄∇⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v7rYVls/@VHbhEe9W@2LIbSWkVXyo@6WRx3tQE7t/zSwaN@jvqme/o@6mg@tN37UNhHICw5yBpIhHp7B/9MUDLnSFIyA2BiITYDYFIgtAA "APL (Dyalog Unicode) – Try It Online")
`{`…`}` "dfn"; `⍵` is argument
 `⍵*2` square the argument
 `s←` assign to `s` (for **s**quare)
 `⍵?` find `n` random indices from 1…`s` without replacement
 `c←` assign to `c` (for **c**andidate)
 `+/` sum them
 `s=` compare to `s`
 `:` if equal
  `c` return the candidate
 `⋄` else
  `∇⍵` recurse on the argument
[Answer]
# [APL (Dyalog Classic)](https://www.dyalog.com/), 18 bytes
```
(≢?≢×≢)⍣(0=+.-∘≢)⍳
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNzkksLs5M/v@ob2pm/qO2CYb/04CkxqPORfZAfHg6kNB81LtYw8BWW0/3UccMCH/z//9pCoZcaQpGQGwMxCZAbArEFgA "APL (Dyalog Classic) – 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`2
`+.-∘≢` subtract the length from each number and sum
`0=` if the sum is 0, stop looping, otherwise try again
[Answer]
# [MATL](https://github.com/lmendo/MATL), ~~18~~ 13 bytes
```
`xGU:GZrtsGU-
```
[Try it online!](https://tio.run/##y00syfn/P6HCPdTKPaqopNg9VPf/f2MA "MATL – 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
```
[Answer]
# Japt, 12 bytes
```
²õ àU ö@²¥Xx
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.6&code=svUg4FUg9kCypVh4&input=NA==)
```
                 :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
```
[Answer]
# [Java (JDK)](http://jdk.java.net/), 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!](https://tio.run/##ZU9Nb8IwDL3zK6xJTAkfEVwXwnESB07sNu2Q0ZSZtW4Vu0wM9bd3Bg1p0iRHz/F7L345xlOcH4vPAeu2yQJHvbtOsHJlR3vBhtzEj/6ROttXkRm2EQkuI4C2e69wDyxRFE4NFlArZ3aSkQ6vbxDzge1NCrAhef59frVLsoYyDDRfX8omGyQB9t5eTjFDDpS@/ux9ySmpwVh/lXKgCXleL7zNLhaF4blW2Eb5cDlS0dTGTlQyXVrrsTTZMX4nY0OgRw5hYXOSLhNk3/eDvyW7J0AIsPQKK8WFNtPpPTzA7sySatd04lr9nZTmYUNtJzDmJ6XHPKaHGc5KF9u2OhvU7TdnP7qefvgB "Java (JDK) – 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.
[Answer]
## 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.
[Answer]
## 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!](https://tio.run/##HY1dboMwEISvEh6KdjFYEKkvSUzUA/QECCUWGMfB2JGhqfg7OzV9mdV8s5p58jfvK6deQ2JsLbaGbWBiyTpmougYO1ZQSr@c4yPIZcmwpB1/wY3lXZIg7a0bdkM/k28@PKjjprYdoE@0qgQkBuOK@Qfx5hocfVpl7uSOsdqho8pU@qcWPdwQWb5PzVEKOP8@lBYg8ywMK8CASZwb62A62ObgcB6Zp2dXdIR8mJKNuQzDAAKYkgyXRf1fvHo9jZc98oRkHpDsNK3rqISuI7euRVoCltve3LL03F6OXgjBypreakG1ldBAi7j9AQ)
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.
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 20 bytes
```
²õ ö¬oU íUõ+)Õæ@²¥Xx
```
[Try it online!](https://ethproductions.github.io/japt/?v=1.4.6&code=svUg9qxvVSDtVfUrKdXmQLKlWHg=&input=MgotUQ==)
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
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 46 bytes
```
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}
```
[Try it online!](https://tio.run/##KypNqvyfZvtf1y6vusrWoDSvJDNHo8o2WstQTy9PKy9WrzgxtyAnVSFPU6@4NNfWFihmXVX731SvJDM3tbi6JrGmQCE6UdvWUCctOjE2tvY/AA "Ruby – Try It Online")
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~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!](https://tio.run/##LY3RCsIwDEXf9xVFUJK1w00f675EhpS6acDFUae2jH177YZ5CPcecnNtcbM2xgEuOA2OeOxgs72Kjbqgnjtg5VVQhJOvOWcd6kp3TwdUl1pKOrEeIKDyRR2kxO@dHi04w1fA3Q64IMyXLSvcH@Tfh@RkOHlMiZT2qSamWtEbYliEcTerhL0bJ/KkP@cGxZSJNK/19Uh9CyWizlbYgRmfBOtl1Sx4oa4d345FqbM5xuMP "C (gcc) – 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.
[Answer]
# [Clean](https://github.com/Ourous/curated-clean-linux), 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 o\e=e rem n^2)(genRandInt(?0)))))
```
[Try it online!](https://tio.run/##JY5BSwMxFITv@RXPUkoKbRG9LaR7qYeFCmKvRXlN3m4DyUvdvAgi/nXjts5hmIGB@Wwg5BqTK4Egoufq4yWNAgdxT/y5ekY5b16RXYqrHQpu9j6LaqFp7jqW9XYy1b4bmxx9K2sxBBAfCWZd083Uj5qz6T07fcwmEA9yhmwMLxa5xFt6e1jqXE6ZPgqxpay5nHTEi/ZsIR3JEIwU4bYbiK8k06Vu75dX1YPgxGpgDo/11/YBh1zX3b7uvhijt//lJaD0aYx/ "Clean – Try It Online")
[Answer]
# [Python](https://docs.python.org/) (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!](https://tio.run/##NYuxDsIwDERn@ApvtdMsRWIJypdUDEFtIVLiRE4Y@PpgBqbT3btXP/1V@DLGISWDBN40Yq5Furkln0J@bAHYNr/eHbZ3xkbes2EyDYpAQmUh17Sjys8dF6twXsgy0Tj0ESEy/NmV3PlUJXLH1gUjwQyTg0nj15Muqn0B "Python 2 – Try It Online")**
Hits max recursion depth at around l(5)
[Answer]
# [Kotlin](https://kotlinlang.org), 32 bytes
```
{(1..it*it).shuffled().take(it)}
```
[Try it online!](https://tio.run/##JYzBCoNADETvfkXwlBS66FWqPRf8iQV3aXAbi8ZexG9fo32nmXkw46SJJf98gtgAvkQJ7h30vOjDSgdt3rB2jvXGSm55rzGmMCA59WNA2/YcV4GPZ0GCrQDjfBNoAefgh54lmHk2UFYlXf7E6WT/@B@@M1uOKETFnuvqAA "Kotlin – Try It Online")
[Answer]
# Mathematica 40 bytes
```
RandomChoice[IntegerPartitions[n^2, {n}]]
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 49 bytes
```
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@18jPCMzJzU6pCi62DYoMS8lPzc4MbcAKALkpKdGK8cZxeoox8Yq2oJY1sWaav9d8qMDijLzSqLTovNiY3Wq83QMdQwNamP/AwA "Wolfram Language (Mathematica) – Try It Online")
Golfed version by @J42161217.
---
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 62 bytes
```
Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n6Zg@z8oMS89NVpZ11DHQEfXMFYbyE/Jz3XOyM9MTnXwzCtJTU8tCkgsKsksyczPK45W1tJQ1jbU1DfSqVaujVX775IfHVCUmVcSnRZtEhurU52nY6hjaFoby4UkkQeXMKiN/Q8A "Wolfram Language (Mathematica) – Try It Online")
### How it works
Mainly based on [this Math.SE question](https://math.stackexchange.com/q/305988). 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](https://math.stackexchange.com/q/1908701). 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!](https://tio.run/##y00syUjNTSzJTE78n6Zg@98nNS@9JMPBM68kNT21KCCxqCSzJDM/rzhaWUtDWdtQU99Ip1q5Nlbtv0t@dEBRZl5JdFp0XmysTnWejqGOoUFt7H8A "Wolfram Language (Mathematica) – Try It Online")
]