CombinationSumIII [source code]

public class CombinationSumIII {
static
/******************************************************************************/
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[10];
        Stack<Integer> accum = new Stack<>();
        dfs(n, k, accum, res, visited, 1);
        return res;
    }

    public void dfs(int sum, int k, Stack<Integer> accum, List<List<Integer>> ls, boolean[] visited, int start) {
        if (sum < k * start || sum > k * 9)
            return;
        if (k == 1) {
            if (!visited[sum] && sum >= start) {
                accum.push(sum);
                ls.add(new ArrayList<Integer>(accum));
                accum.pop();
            }
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (!visited[i]) {
                visited[i] = true;
                accum.push(i);
                dfs(sum - i, k - 1, accum, ls, visited, i + 1);
                accum.pop();
                visited[i] = false;
            }
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        CombinationSumIII.Solution tester = new CombinationSumIII.Solution();
    }
}

标准的backtracking题目, 应该不难写;

明明是一个很简单的题目, 最后却花了三十多分钟才AC, 很丢人好吧. 最后的速度是2ms (10%), 一般性, 这个题目大概就是这个速度范围了;

难点一个就是第一行的pruning, 这个其实也不难; 然后要有一个accum, 因为是backtracking. 这里认为Stack更方便, 因为undo更简单一些; 然后要有一个start; 注意, 这里的visited的array才是用来在backtracking中bookkeep的, 而这个start的作用其实是impose order to remove duplicate;

这个是submission最优解: 1ms

class Solution {  
    public List<List<Integer>> combinationSum3(int k, int n) {  
        List<List<Integer>> result = new ArrayList<>();  
        List<Integer> path = new ArrayList<>();  
        dfs(k, n, 1, path, result);  
        return result;  
    }  

    public void dfs(int k, int n, int i, List<Integer> path, List<List<Integer>> result){  
        if (i > n || k == 0 || i >= 10) return; // dont forget that i < 10!  

        if (i == n && k == 1){  
            path.add(i);  
            result.add(new ArrayList<Integer>(path));  
            path.remove(path.size() - 1);  
            return;  
        }  

        dfs(k, n, i+1, path, result);  
        path.add(i);  
        dfs(k-1, n-i, i+1, path, result);  
        path.remove(path.size() - 1);  
        return;  
    }  
}

写法还是比较清奇的, 注意他这里两点:

• 当我们用start来impose order之后, 其实我们是不需要visited这个array来记录了的;
• 关于这个start, 你有没有发现其实它还代表了一些其他的东西? 带入了这个start来缩小搜索范围之后, 这个问题其实就有了一个subproblem的概念了; 而他这里的recursion的写法也非常类似DP的写法, 因为他这里有一个decision的过程! do we include this number(i). 这个还是我第一次见到backtracking这么写, 以前的backtracking, 每一个iteration思考的内容主要是, which/what to pick, 而这里的写法是whether. 很少见, 但是不见得不可以;
  • 我思考了一下, 我认为, 如果是要用whether的概念来写backtracking的话, 肯定要保证这个算法能够产生一个subproblem的概念; 事实上, subproblem这个概念的作用就有点类似visited这个flag array;

这个是discussion最优解:

 public List<List<Integer>> combinationSum3(int k, int n) {  
    List<List<Integer>> ans = new ArrayList<>();  
    combination(ans, new ArrayList<Integer>(), k, 1, n);  
    return ans;  
}  

private void combination(List<List<Integer>> ans, List<Integer> comb, int k,  int start, int n) {  
    if (comb.size() == k && n == 0) {  
        List<Integer> li = new ArrayList<Integer>(comb);  
        ans.add(li);  
        return;  
    }  
    for (int i = start; i <= 9; i++) {  
        comb.add(i);  
        combination(ans, comb, k, i+1, n-i);  
        comb.remove(comb.size() - 1);  
    }  
}

思路跟我的类似, 但是可以看到, visited这个东西确实是没有必要了, 一个start就足够了; 另外这里还有一个抉择就是之前提到的, check leaf or check null. 我的选择其实更多的是类似check leaf, 而他这里的选择其实是check Null; 好像这一题check Null并不是一个坏事, 因为check leaf的话, leaf要专门写一个case, 这个case里面其实还有类似push/pop这一套的操作, 跟下面的recursive call的case的内容其实是有一点重复的. 所以check Null的话就可以把代码分成简单的两种情况, 需要操作的和整个的不需要操作的;

这个是底下一个人提出的优化:

    private static void combination(List<List<Integer>> ans, List<Integer> comb, int k,  int start, int n) {  
        if (comb.size() > k) {  
            return;  
        }  
        if (comb.size() == k && n == 0) {  
            List<Integer> li = new ArrayList<Integer>(comb);  
            ans.add(li);  
            return;  
        }  
        for (int i = start; i <= n && i<=9; i++) {  

                comb.add(i);  
                combination(ans, comb, k, i+1, n-i);  
                comb.remove(comb.size() - 1);  

        }  
    }

其实就是一个pruning. 我自己的解法是有这个内容的, 不过是写在base case里面了(这个也是一个之前讨论过的Trade-Off, prevent In or force Out).

discussion基本没有什么其他的解法了; 不过这个问题确实也就是非常textbook的backtracking. 也不好有什么其他奇葩的解法了;

关于复杂度, 我的解法感觉应该是A(9, k) * 10这样的? 因为有fanning. 这里fanning选择10肯定是不tight的, 但是不这样选又不好算了;

whether写法的那个其实好像也差不多, 反正recursion的深度就是用k来控制的;

Problem Description

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:  

[[1,2,4]]

Example 2:

Input: k = 3, n = 9  

Output:  

[[1,2,6], [1,3,5], [2,3,4]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:71.6K
Total Submissions:158.8K
Contributor: LeetCode
Related Topics
array backtracking
Similar Questions
Combination Sum