216. Combination Sum III.md

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);
            }
        }
    }
}

C++ version

• Method 1:recursion

   class Solution {
   	vector<vector<int>> res_;
   	void dfs(vector<int>& temp, int target, int index, int sum, int k){
   		if(temp.size() == k && sum == target){
   			res_.emplace_back(temp);
   		}else if(sum < target && temp.size() < k){
   			for(int i = index; i <= 9; ++i){
   				temp.emplace_back(i);
   				dfs(temp, target, i + 1, sum + i, k);
   				temp.pop_back();
   			}
   		}
   	}
   public:
   	vector<vector<int>> combinationSum3(int k, int n) {
   		vector<int> temp;
   		dfs(temp, n, 1, 0, k);
   		return res_;
   	}
   };