next_permutation の要領で自然数の分割を列挙することで \(O(N p(N))\) 時間で解くことができます。

解法

\(A\) が自然数 \(N\) の分割であるとして、\(A\) よりも辞書順で大きな辞書順最小の \(N\) の分割を求めましょう。

1. 後ろから見て最初に増加する箇所を探し、\(A_i\) とおきます。（もう少し厳密にいうと \(A_i \gt A_{i + 1} = A_{i + 2} = \dots\)、ただし \(A_i\) は末尾ではありません。）
2. \(A_i\) を \(1\) 増やし、あまりをすべて \(1\) にします。

逆順に走査することもできます。

pub fn next_partition(a: &mut Vec<usize>) -> bool {
    let Some(mut sum) = a.pop() else { return false };
    if a.is_empty() {
        return false;
    }
    while let Some(x) = a.pop() {
        sum += x;
        if a.last().map_or(true, |&last| last > x) {
            a.push(x + 1);
            a.extend(std::iter::repeat(1).take(sum - x - 1));
            break;
        }
    }
    true
}
pub fn prev_partition(a: &mut Vec<usize>) -> bool {
    let Some(i) = a.iter().rposition(|&x| x != 1) else { return false };
    let max = a[i] - 1;
    let mut sum = a.split_off(i).into_iter().sum::<usize>();
    while sum >= max {
        a.push(max);
        sum -= max;
    }
    if sum > 0 {
        a.push(sum);
    }
    true
}

参考記事: next_permutation と同様に列挙できるもの一覧

提出

Rust (118 ms): https://atcoder.jp/contests/abc226/submissions/47515126