<p>An integer <code>x</code> is <strong>numerically balanced</strong> if for every digit <code>d</code> in the number <code>x</code>, there are <strong>exactly</strong> <code>d</code> occurrences of that digit in <code>x</code>.</p>

<p>Given an integer <code>n</code>, return <em>the <strong>smallest numerically balanced</strong> number <strong>strictly greater</strong> than </em><code>n</code><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 22
<strong>Explanation:</strong> 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1000
<strong>Output:</strong> 1333
<strong>Explanation:</strong> 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3000
<strong>Output:</strong> 3133
<strong>Explanation:</strong> 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        def distribute(sum: int, s: int, L: int) -> List[List[int]]:
            if s+sum == L: return [[s]]
            res = []
            for i in range(s+1, L+1):
                for e in distribute(sum+s, i, L):
                    e.append(s)
                    res.append(e)
            return res
        
        def combo(L):
            coll = []
            for i in range(1, L+1):
                coll.extend(distribute(0, i, L))
            return coll

        def toPerm(c):
            p = []
            for i in range(len(c)-1, -1, -1):
                for j in range(c[i]): p.append(c[i])
            return p

        def toInt(p):
            res = 0
            for v in p: res = res * 10 + v
            return res

        def nextPerm(p):
            i = len(p) - 2
            while i >= 0 and p[i] >= p[i+1]: i-=1
            if i < 0: return False

            j = len(p)-1
            while p[j] <= p[i]: j-=1
            p[i], p[j] = p[j], p[i]
            lo, hi = i+1, len(p)-1
            while lo < hi: 
                p[lo], p[hi] = p[hi], p[lo]
                lo+=1; hi-=1
            return True

        res = toInt(toPerm(combo(len(str(n))+1)[0]))
        for c in combo(len(str(n))):
            p = toPerm(c)
            while toInt(p) <= n: 
                if not nextPerm(p): break
            if toInt(p) > n: 
                res = min(res, toInt(p))
        return res
16800