leetCode：216. Combination Sum III

leetCodeの「216. Combination Sum III」を解いた。(苦手な) dfs の良い練習になったので、今後の参考にため、書いたコードをここに残しておく。
https://leetcode.com/problems/combination-sum-iii/

class Solution {
    private int numCount;
    private int targetSum;

    public List<List<Integer>> combinationSum3(int k, int n) {
        numCount = k;
        targetSum = n;
        List<List<Integer>> result = new ArrayList<>();
        dfsHelper(1, 0, new ArrayList<>(), result);

        return result;
    }

    // 各 soFar の状態で、startNum (以降) を処理する。各 soFar に startNum は未だ反映されていない状態。
    // ★ numsSoFar は使い回すので取り扱い要注意。
    private void dfsHelper(int startNum, int sumSoFar, List<Integer> numsSoFar, List<List<Integer>> result) {
        if (numsSoFar.size() > numCount || sumSoFar > targetSum) {
            return;
        }

        // 条件を満たすので、numsSoFar をコピーしてから result に add して、return する。
        if (numsSoFar.size() == numCount && sumSoFar == targetSum) {
            result.add(new ArrayList<>(numsSoFar));
            return;
        }

        // 次の数値を選択する。この for 文内ではバックトラック法を使う。
        for (int i = startNum; i <= 9; i++) {
            numsSoFar.add(i);

            // i を選択した状態で、i + 1 の試行に入っていく。
            dfsHelper(i + 1, sumSoFar + i, numsSoFar, result);

            // バックトラックのため戻している。
            numsSoFar.remove(numsSoFar.size() - 1);
        }
    }
}