216. Combination Sum III

Question

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.

Note:

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Thinking:

  • Method 1：sort
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if(k == 0) return result;
        backtrace(result, new ArrayList<Integer>(), new boolean[9], n, 0, k, 1);
        return result;
    }
    private void backtrace(List<List<Integer>> result, List<Integer> list, boolean[] used, int target, int sum, int k, int start){
        if(sum == target && list.size() == k){
            result.add(new ArrayList<Integer>(list));
        }else if(sum > target)
            return;
        else{
            for(int i = start; i <= 9; i++){
                if(used[i - 1]) continue;
                used[i - 1] = true;
                list.add(i);
                backtrace(result, list, used, target, sum + i, k, i + 1);
                list.remove(list.size() - 1);
                used[i - 1] = false;
            }
        }
    }
}

二刷

  1. Use backtrace to evaluate.
  2. Break out point: check the size of the array and the sum of the numbers in current array. 
    class Solution {
 public List<List<Integer>> combinationSum3(int k, int n) {
     List<List<Integer>> result = new LinkedList<>();
     List<Integer> temp = new LinkedList<>();
     backtrace(k, n, temp, result, 0, 1);
     return result;
 }
    
 private void backtrace(int k, int n, List<Integer> temp, List<List<Integer>> result, int sum, int cur){
     if(temp.size() == k){
         if(sum == n){
             List<Integer> copy = new LinkedList<>(temp);
             result.add(copy);
         }
     }else{
         for(int i = cur; i <= 9; i++){
             temp.add(i);
             backtrace(k, n, temp, result, sum + i, i + 1);
             temp.remove(temp.size() - 1);
         }
     }
 }
}

Third time

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new LinkedList<>();
        dfs(result, n, k, 0, new LinkedList<Integer>(), 1);
        return result;
    }
    private void dfs(List<List<Integer>> result, int n, int k, int sum, List<Integer> temp, int index){
        if(sum == n && temp.size() == k) result.add(new LinkedList<Integer>(temp));
        else if(sum < n && temp.size() < k){
            for(int i = index; i <= 9; i++){
                if(i + sum > n) break;
                temp.add(i);
                dfs(result, n, k, sum + i, temp, i + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }
}