\(N\) の桁数を \(S\) とし，数字の数を \(B=10\) とします． 以下の解法は，実装次第ですが，\(O(B (2^B + S))\) 時間や \(O(B^2 S)\) 時間程度になると思います（本問題の制約だと前者の方が速い）．

数え上げる対象となる整数について，以下のパターンに分けて考えてみます．

• \(N\) と最初の \(k\) 桁が一致し，\(k+1\) 桁目は \(N\) と一致しないような \(S\) 桁の整数（\(k = 0,1, \ldots, S-1\)）
• \(k\) 桁の整数（\(k=1,2,\ldots, S-1\)）
• \(N\) そのもの

1つ目の場合については \(k+1\) 桁目の値，2つ目の場合に対しては最上位の桁は全探索します． これにより，\(O(BS)\) 個の場合について考えれば良いことになります． 3つ目の場合については，条件を満たすかどうか判定するだけですので，以降は1つ目の場合と，2つ目の場合を考えます．

1つ目の場合・2つ目の場合ともに，全探索した桁より下位の桁については，満たすべき条件は

• 桁数（先頭は0でも良い）
• 必ず使わないといけない数字の集合

ここまで来ると，数字には対称性がありますので，動的計画法で，（桁数，使わないといけない数字の種類数）を状態に，条件を満たす整数の個数を数え上げることができます． また，それと同時に，全ての条件を満たすものを書き出したときの， 例えば，使わないといけない数字と使わなくても良い数字の出てくる個数の比率なども動的計画法で計算することができます．

この情報をもとに，1つ目の場合，2つ目の場合についても，条件を満たす整数の和を計算でき，この問題の答えを求めることができます．