Leetcode - Combination Sum III

My code:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k <= 0 || k > 9 || n <= 0)
            return result;
        ArrayList<Integer> combination = new ArrayList<Integer>();
        getCombinations(1, 1, k, 0, n, combination, result);
        return result;
    }
    
    private void getCombinations(int begin, int count, int k, int sum, int n,
                                ArrayList<Integer> combination, ArrayList<List<Integer>> result) {
        if (count > k)
            return;
        else {
            for (int i = begin; i <= 9; i++) {
                int temp = sum + i;
                if (temp > n)
                    break;
                else if (temp == n) {
                    if (count < k)
                        break;
                    else {
                        combination.add(i);
                        result.add(new ArrayList<Integer>(combination));
                        combination.remove(combination.size() - 1);
                        break;
                    }
                }
                else {
                    combination.add(i);
                    getCombinations(i + 1, count + 1, k, temp, n, combination, result);
                    combination.remove(combination.size() - 1);
                }
            
            }
        }
        
    }
}

My test result:

Paste_Image.png

还是差不多的思路。然后需要限定长度是k，所以加了一个统计个数的count

**
总结： Array， DFS
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (k < 1 || n < 1)
            return ret;
        ArrayList<Integer> group = new ArrayList<Integer>();
        helper(1, 0, 0, k, n, ret, group);
        return ret;
    }
    
    private void helper(int begin, int sum, int numbers, int k, int n,
                            ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
        if (numbers >= k) { // if numbers == k, then detect whether sum == n
            if (sum != n) {
                return;
            }
            else {
                ret.add(new ArrayList<Integer>(group));
                return;
            }
        }
        else if (sum >= n) // if numbers < k and sum >= n, then return without consideration of sum
            return;
        else { // if numbers < k and sum < n, then explore it with dfs
            for (int i = begin; i < 10; i++) {
                group.add(i);
                helper(i + 1, sum + i, numbers + 1, k, n, ret, group);
                group.remove(group.size() - 1);
            }
        }
    }
}

感觉我这次写的逻辑更加清晰。没什么难度。

Anyway, Good luck, Richardo!