leetcode216. Combination Sum III

216. Combination Sum III

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.

Example 1:

Input: k = 3, n = 7

Output:

Example 2:

Input: k = 3, n = 9

Output:

[[,,], [,,], [,,]]
           

解法

回溯法，有序的，不包括本元素，并且判断条件增加temp.size() == num

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] candidates = new int[];
        for (int i = ; i < candidates.length; i++) {
            candidates[i] = i + ;
        }
        List<List<Integer>> ret = new ArrayList<>();
        if (candidates == null || candidates.length ==  || n <= ) {
            return ret;
        }
        Arrays.sort(candidates);
        backtrack(ret, new ArrayList<Integer>(), candidates, n, k, );
        return ret;
    }
    private void backtrack(List<List<Integer>> ret, List<Integer> temp, int[] candidates, int remain, int num, int start) {
        if (remain ==  && temp.size() == num) {
            ret.add(new ArrayList<Integer>(temp));
        } else if (remain <  || temp.size() > num) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] == candidates[i] - ) continue;
            temp.add(candidates[i]);
            backtrack(ret, temp, candidates, remain - candidates[i], num, i + );
            temp.remove(temp.size() - );
        }
    }
}
           

解法二

解法一的优化

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ret = new ArrayList<>();
        backtrack(ret, new ArrayList<Integer>(), n, k, );
        return ret;
    }
    private void backtrack(List<List<Integer>> ret, List<Integer> temp, int remain, int num, int start) {
        if (remain ==  && temp.size() == num) {
            ret.add(new ArrayList<Integer>(temp));
        } else if (remain <  || temp.size() > num) {
            return;
        }
        for (int i = start; i <= ; i++) {
            temp.add(i);
            backtrack(ret, temp, remain - i, num, i + );
            temp.remove(temp.size() - );
        }
    }
}