Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Solution 1 : DFS

k numbers that add up to a number n.

{
                1     2      3       4 ..... 9
              / \     /\   /   \    / \      /\
             23..9   3..9  4...9   5...9

}

base case : resCell.size() == k && sum == T

public void dfs(List<List<Integer>> res, List<Integer> resCell, int sum, int k, int target, int start) {
    if (sum > target) {
        return;
    }
    if (resCell.size() == k) {
        if (sum == target) {
            res.add(new ArrayList<Integer>(resCell));
            return;
        }
    }
    //pruning here: if remaining size  + current res size is not enough for k.
    if (resCell.size() + 9 - start + 1 < k) {
        return;
    }
    for(int i = start; i <= 9; i++) {
        resCell.add(i);
        dfs(res,resCell,sum + i, k, target, i + 1);
        resCell.remove(resCell.size() - 1);
    }
}