2017-06-27 04:07:00 +0000   |     algorithm leetcode backtracking   |   Viewed times   |    

题目

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]]

主要思路:用回溯算法模拟 “指针法”

首先,遇到这种问题,用标准的“回溯算法” 可以完整尝试所有可能的排列组合。排序,去重之后可以去掉相同数字集合的不同排列项。

Input: k = 3, n = 7

正确答案:
[[1,2,4]]

标准回溯算法,返回的是全排列:
[[1,2,4],[1,4,2],[2,1,4],[2,4,1],[4,1,2],[4,2,1]]

一般来说用Two Pointers指针法,可以直接排除掉相同元素,不同排列的干扰。

最重要的一个原则是:下一个指针,不是从头开始遍历,而是从前一个指针的下一个元素开始。

也就是无论i等于多少,j start from i+1。无论j等于多少,k start from j+1

Input: k = 3, n = 7

用三个指针i,j,k, 从左往右遍历:

     i j k
     | | |
    [1,2,3,4,5,6,7,8,9]

直接得到正确结果,
[[1,2,4]]

在回溯算法中,可以用一个参数int start模拟这个指针的功能。

代码如下

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> buffer = new ArrayList<>();
        backtracking(k,n,buffer,1,result);
        return result;
    }
    /**
     * 用 int start 模拟 pointer
     */
    private void backtracking(int k, int n, List<Integer> buffer, int start, List<List<Integer>> memo) {
        if (k == 0) {
            if (n == 0) { memo.add(new ArrayList<Integer>(buffer)); }
            return;
        }
        if (n <= 0) { return; } // 提前剪枝
        for (int i = start; i < 10; i++) {
            buffer.add(i);
            backtracking(k-1,n-i,buffer,i+1,memo);
            buffer.remove(buffer.size()-1);
        }
    }
}

结果

combination-sum-three-1

表驱动法

其实如果只是数字1-9,可能的组合非常有限,如果提前把所有结果计算好,存在表里,就可以以 的时间查询。

>>>>>> Sum to 1 <<<<<<
[[1]]



>>>>>> Sum to 2 <<<<<<
[[2]]



>>>>>> Sum to 3 <<<<<<
[[3]]
[[1, 2]]



>>>>>> Sum to 4 <<<<<<
[[4]]
[[1, 3]]



>>>>>> Sum to 5 <<<<<<
[[5]]
[[1, 4], [2, 3]]



>>>>>> Sum to 6 <<<<<<
[[6]]
[[1, 5], [2, 4]]
[[1, 2, 3]]



>>>>>> Sum to 7 <<<<<<
[[7]]
[[1, 6], [2, 5], [3, 4]]
[[1, 2, 4]]



>>>>>> Sum to 8 <<<<<<
[[8]]
[[1, 7], [2, 6], [3, 5]]
[[1, 2, 5], [1, 3, 4]]



>>>>>> Sum to 9 <<<<<<
[[9]]
[[1, 8], [2, 7], [3, 6], [4, 5]]
[[1, 2, 6], [1, 3, 5], [2, 3, 4]]



>>>>>> Sum to 10 <<<<<<
[[1, 9], [2, 8], [3, 7], [4, 6]]
[[1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5]]
[[1, 2, 3, 4]]



>>>>>> Sum to 11 <<<<<<
[[2, 9], [3, 8], [4, 7], [5, 6]]
[[1, 2, 8], [1, 3, 7], [1, 4, 6], [2, 3, 6], [2, 4, 5]]
[[1, 2, 3, 5]]



>>>>>> Sum to 12 <<<<<<
[[3, 9], [4, 8], [5, 7]]
[[1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5]]
[[1, 2, 3, 6], [1, 2, 4, 5]]



>>>>>> Sum to 13 <<<<<<
[[4, 9], [5, 8], [6, 7]]
[[1, 3, 9], [1, 4, 8], [1, 5, 7], [2, 3, 8], [2, 4, 7], [2, 5, 6], [3, 4, 6]]
[[1, 2, 3, 7], [1, 2, 4, 6], [1, 3, 4, 5]]



>>>>>> Sum to 14 <<<<<<
[[5, 9], [6, 8]]
[[1, 4, 9], [1, 5, 8], [1, 6, 7], [2, 3, 9], [2, 4, 8], [2, 5, 7], [3, 4, 7], [3, 5, 6]]
[[1, 2, 3, 8], [1, 2, 4, 7], [1, 2, 5, 6], [1, 3, 4, 6], [2, 3, 4, 5]]



>>>>>> Sum to 15 <<<<<<
[[6, 9], [7, 8]]
[[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 5, 8], [2, 6, 7], [3, 4, 8], [3, 5, 7], [4, 5, 6]]
[[1, 2, 3, 9], [1, 2, 4, 8], [1, 2, 5, 7], [1, 3, 4, 7], [1, 3, 5, 6], [2, 3, 4, 6]]
[[1, 2, 3, 4, 5]]



>>>>>> Sum to 16 <<<<<<
[[7, 9]]
[[1, 6, 9], [1, 7, 8], [2, 5, 9], [2, 6, 8], [3, 4, 9], [3, 5, 8], [3, 6, 7], [4, 5, 7]]
[[1, 2, 4, 9], [1, 2, 5, 8], [1, 2, 6, 7], [1, 3, 4, 8], [1, 3, 5, 7], [1, 4, 5, 6], [2, 3, 4, 7], [2, 3, 5, 6]]
[[1, 2, 3, 4, 6]]



>>>>>> Sum to 17 <<<<<<
[[8, 9]]
[[1, 7, 9], [2, 6, 9], [2, 7, 8], [3, 5, 9], [3, 6, 8], [4, 5, 8], [4, 6, 7]]
[[1, 2, 5, 9], [1, 2, 6, 8], [1, 3, 4, 9], [1, 3, 5, 8], [1, 3, 6, 7], [1, 4, 5, 7], [2, 3, 4, 8], [2, 3, 5, 7], [2, 4, 5, 6]]
[[1, 2, 3, 4, 7], [1, 2, 3, 5, 6]]



>>>>>> Sum to 18 <<<<<<
[[1, 8, 9], [2, 7, 9], [3, 6, 9], [3, 7, 8], [4, 5, 9], [4, 6, 8], [5, 6, 7]]
[[1, 2, 6, 9], [1, 2, 7, 8], [1, 3, 5, 9], [1, 3, 6, 8], [1, 4, 5, 8], [1, 4, 6, 7], [2, 3, 4, 9], [2, 3, 5, 8], [2, 3, 6, 7], [2, 4, 5, 7], [3, 4, 5, 6]]
[[1, 2, 3, 4, 8], [1, 2, 3, 5, 7], [1, 2, 4, 5, 6]]



>>>>>> Sum to 19 <<<<<<
[[2, 8, 9], [3, 7, 9], [4, 6, 9], [4, 7, 8], [5, 6, 8]]
[[1, 2, 7, 9], [1, 3, 6, 9], [1, 3, 7, 8], [1, 4, 5, 9], [1, 4, 6, 8], [1, 5, 6, 7], [2, 3, 5, 9], [2, 3, 6, 8], [2, 4, 5, 8], [2, 4, 6, 7], [3, 4, 5, 7]]
[[1, 2, 3, 4, 9], [1, 2, 3, 5, 8], [1, 2, 3, 6, 7], [1, 2, 4, 5, 7], [1, 3, 4, 5, 6]]



>>>>>> Sum to 20 <<<<<<
[[3, 8, 9], [4, 7, 9], [5, 6, 9], [5, 7, 8]]
[[1, 2, 8, 9], [1, 3, 7, 9], [1, 4, 6, 9], [1, 4, 7, 8], [1, 5, 6, 8], [2, 3, 6, 9], [2, 3, 7, 8], [2, 4, 5, 9], [2, 4, 6, 8], [2, 5, 6, 7], [3, 4, 5, 8], [3, 4, 6, 7]]
[[1, 2, 3, 5, 9], [1, 2, 3, 6, 8], [1, 2, 4, 5, 8], [1, 2, 4, 6, 7], [1, 3, 4, 5, 7], [2, 3, 4, 5, 6]]



>>>>>> Sum to 21 <<<<<<
[[4, 8, 9], [5, 7, 9], [6, 7, 8]]
[[1, 3, 8, 9], [1, 4, 7, 9], [1, 5, 6, 9], [1, 5, 7, 8], [2, 3, 7, 9], [2, 4, 6, 9], [2, 4, 7, 8], [2, 5, 6, 8], [3, 4, 5, 9], [3, 4, 6, 8], [3, 5, 6, 7]]
[[1, 2, 3, 6, 9], [1, 2, 3, 7, 8], [1, 2, 4, 5, 9], [1, 2, 4, 6, 8], [1, 2, 5, 6, 7], [1, 3, 4, 5, 8], [1, 3, 4, 6, 7], [2, 3, 4, 5, 7]]
[[1, 2, 3, 4, 5, 6]]



>>>>>> Sum to 22 <<<<<<
[[5, 8, 9], [6, 7, 9]]
[[1, 4, 8, 9], [1, 5, 7, 9], [1, 6, 7, 8], [2, 3, 8, 9], [2, 4, 7, 9], [2, 5, 6, 9], [2, 5, 7, 8], [3, 4, 6, 9], [3, 4, 7, 8], [3, 5, 6, 8], [4, 5, 6, 7]]
[[1, 2, 3, 7, 9], [1, 2, 4, 6, 9], [1, 2, 4, 7, 8], [1, 2, 5, 6, 8], [1, 3, 4, 5, 9], [1, 3, 4, 6, 8], [1, 3, 5, 6, 7], [2, 3, 4, 5, 8], [2, 3, 4, 6, 7]]
[[1, 2, 3, 4, 5, 7]]



>>>>>> Sum to 23 <<<<<<
[[6, 8, 9]]
[[1, 5, 8, 9], [1, 6, 7, 9], [2, 4, 8, 9], [2, 5, 7, 9], [2, 6, 7, 8], [3, 4, 7, 9], [3, 5, 6, 9], [3, 5, 7, 8], [4, 5, 6, 8]]
[[1, 2, 3, 8, 9], [1, 2, 4, 7, 9], [1, 2, 5, 6, 9], [1, 2, 5, 7, 8], [1, 3, 4, 6, 9], [1, 3, 4, 7, 8], [1, 3, 5, 6, 8], [1, 4, 5, 6, 7], [2, 3, 4, 5, 9], [2, 3, 4, 6, 8], [2, 3, 5, 6, 7]]
[[1, 2, 3, 4, 5, 8], [1, 2, 3, 4, 6, 7]]



>>>>>> Sum to 24 <<<<<<
[[7, 8, 9]]
[[1, 6, 8, 9], [2, 5, 8, 9], [2, 6, 7, 9], [3, 4, 8, 9], [3, 5, 7, 9], [3, 6, 7, 8], [4, 5, 6, 9], [4, 5, 7, 8]]
[[1, 2, 4, 8, 9], [1, 2, 5, 7, 9], [1, 2, 6, 7, 8], [1, 3, 4, 7, 9], [1, 3, 5, 6, 9], [1, 3, 5, 7, 8], [1, 4, 5, 6, 8], [2, 3, 4, 6, 9], [2, 3, 4, 7, 8], [2, 3, 5, 6, 8], [2, 4, 5, 6, 7]]
[[1, 2, 3, 4, 5, 9], [1, 2, 3, 4, 6, 8], [1, 2, 3, 5, 6, 7]]



>>>>>> Sum to 25 <<<<<<
[[1, 7, 8, 9], [2, 6, 8, 9], [3, 5, 8, 9], [3, 6, 7, 9], [4, 5, 7, 9], [4, 6, 7, 8]]
[[1, 2, 5, 8, 9], [1, 2, 6, 7, 9], [1, 3, 4, 8, 9], [1, 3, 5, 7, 9], [1, 3, 6, 7, 8], [1, 4, 5, 6, 9], [1, 4, 5, 7, 8], [2, 3, 4, 7, 9], [2, 3, 5, 6, 9], [2, 3, 5, 7, 8], [2, 4, 5, 6, 8], [3, 4, 5, 6, 7]]
[[1, 2, 3, 4, 6, 9], [1, 2, 3, 4, 7, 8], [1, 2, 3, 5, 6, 8], [1, 2, 4, 5, 6, 7]]



>>>>>> Sum to 26 <<<<<<
[[2, 7, 8, 9], [3, 6, 8, 9], [4, 5, 8, 9], [4, 6, 7, 9], [5, 6, 7, 8]]
[[1, 2, 6, 8, 9], [1, 3, 5, 8, 9], [1, 3, 6, 7, 9], [1, 4, 5, 7, 9], [1, 4, 6, 7, 8], [2, 3, 4, 8, 9], [2, 3, 5, 7, 9], [2, 3, 6, 7, 8], [2, 4, 5, 6, 9], [2, 4, 5, 7, 8], [3, 4, 5, 6, 8]]
[[1, 2, 3, 4, 7, 9], [1, 2, 3, 5, 6, 9], [1, 2, 3, 5, 7, 8], [1, 2, 4, 5, 6, 8], [1, 3, 4, 5, 6, 7]]



>>>>>> Sum to 27 <<<<<<
[[3, 7, 8, 9], [4, 6, 8, 9], [5, 6, 7, 9]]
[[1, 2, 7, 8, 9], [1, 3, 6, 8, 9], [1, 4, 5, 8, 9], [1, 4, 6, 7, 9], [1, 5, 6, 7, 8], [2, 3, 5, 8, 9], [2, 3, 6, 7, 9], [2, 4, 5, 7, 9], [2, 4, 6, 7, 8], [3, 4, 5, 6, 9], [3, 4, 5, 7, 8]]
[[1, 2, 3, 4, 8, 9], [1, 2, 3, 5, 7, 9], [1, 2, 3, 6, 7, 8], [1, 2, 4, 5, 6, 9], [1, 2, 4, 5, 7, 8], [1, 3, 4, 5, 6, 8], [2, 3, 4, 5, 6, 7]]



>>>>>> Sum to 28 <<<<<<
[[4, 7, 8, 9], [5, 6, 8, 9]]
[[1, 3, 7, 8, 9], [1, 4, 6, 8, 9], [1, 5, 6, 7, 9], [2, 3, 6, 8, 9], [2, 4, 5, 8, 9], [2, 4, 6, 7, 9], [2, 5, 6, 7, 8], [3, 4, 5, 7, 9], [3, 4, 6, 7, 8]]
[[1, 2, 3, 5, 8, 9], [1, 2, 3, 6, 7, 9], [1, 2, 4, 5, 7, 9], [1, 2, 4, 6, 7, 8], [1, 3, 4, 5, 6, 9], [1, 3, 4, 5, 7, 8], [2, 3, 4, 5, 6, 8]]
[[1, 2, 3, 4, 5, 6, 7]]



>>>>>> Sum to 29 <<<<<<
[[5, 7, 8, 9]]
[[1, 4, 7, 8, 9], [1, 5, 6, 8, 9], [2, 3, 7, 8, 9], [2, 4, 6, 8, 9], [2, 5, 6, 7, 9], [3, 4, 5, 8, 9], [3, 4, 6, 7, 9], [3, 5, 6, 7, 8]]
[[1, 2, 3, 6, 8, 9], [1, 2, 4, 5, 8, 9], [1, 2, 4, 6, 7, 9], [1, 2, 5, 6, 7, 8], [1, 3, 4, 5, 7, 9], [1, 3, 4, 6, 7, 8], [2, 3, 4, 5, 6, 9], [2, 3, 4, 5, 7, 8]]
[[1, 2, 3, 4, 5, 6, 8]]



>>>>>> Sum to 30 <<<<<<
[[6, 7, 8, 9]]
[[1, 5, 7, 8, 9], [2, 4, 7, 8, 9], [2, 5, 6, 8, 9], [3, 4, 6, 8, 9], [3, 5, 6, 7, 9], [4, 5, 6, 7, 8]]
[[1, 2, 3, 7, 8, 9], [1, 2, 4, 6, 8, 9], [1, 2, 5, 6, 7, 9], [1, 3, 4, 5, 8, 9], [1, 3, 4, 6, 7, 9], [1, 3, 5, 6, 7, 8], [2, 3, 4, 5, 7, 9], [2, 3, 4, 6, 7, 8]]
[[1, 2, 3, 4, 5, 6, 9], [1, 2, 3, 4, 5, 7, 8]]



>>>>>> Sum to 31 <<<<<<
[[1, 6, 7, 8, 9], [2, 5, 7, 8, 9], [3, 4, 7, 8, 9], [3, 5, 6, 8, 9], [4, 5, 6, 7, 9]]
[[1, 2, 4, 7, 8, 9], [1, 2, 5, 6, 8, 9], [1, 3, 4, 6, 8, 9], [1, 3, 5, 6, 7, 9], [1, 4, 5, 6, 7, 8], [2, 3, 4, 5, 8, 9], [2, 3, 4, 6, 7, 9], [2, 3, 5, 6, 7, 8]]
[[1, 2, 3, 4, 5, 7, 9], [1, 2, 3, 4, 6, 7, 8]]



>>>>>> Sum to 32 <<<<<<
[[2, 6, 7, 8, 9], [3, 5, 7, 8, 9], [4, 5, 6, 8, 9]]
[[1, 2, 5, 7, 8, 9], [1, 3, 4, 7, 8, 9], [1, 3, 5, 6, 8, 9], [1, 4, 5, 6, 7, 9], [2, 3, 4, 6, 8, 9], [2, 3, 5, 6, 7, 9], [2, 4, 5, 6, 7, 8]]
[[1, 2, 3, 4, 5, 8, 9], [1, 2, 3, 4, 6, 7, 9], [1, 2, 3, 5, 6, 7, 8]]



>>>>>> Sum to 33 <<<<<<
[[3, 6, 7, 8, 9], [4, 5, 7, 8, 9]]
[[1, 2, 6, 7, 8, 9], [1, 3, 5, 7, 8, 9], [1, 4, 5, 6, 8, 9], [2, 3, 4, 7, 8, 9], [2, 3, 5, 6, 8, 9], [2, 4, 5, 6, 7, 9], [3, 4, 5, 6, 7, 8]]
[[1, 2, 3, 4, 6, 8, 9], [1, 2, 3, 5, 6, 7, 9], [1, 2, 4, 5, 6, 7, 8]]



>>>>>> Sum to 34 <<<<<<
[[4, 6, 7, 8, 9]]
[[1, 3, 6, 7, 8, 9], [1, 4, 5, 7, 8, 9], [2, 3, 5, 7, 8, 9], [2, 4, 5, 6, 8, 9], [3, 4, 5, 6, 7, 9]]
[[1, 2, 3, 4, 7, 8, 9], [1, 2, 3, 5, 6, 8, 9], [1, 2, 4, 5, 6, 7, 9], [1, 3, 4, 5, 6, 7, 8]]



>>>>>> Sum to 35 <<<<<<
[[5, 6, 7, 8, 9]]
[[1, 4, 6, 7, 8, 9], [2, 3, 6, 7, 8, 9], [2, 4, 5, 7, 8, 9], [3, 4, 5, 6, 8, 9]]
[[1, 2, 3, 5, 7, 8, 9], [1, 2, 4, 5, 6, 8, 9], [1, 3, 4, 5, 6, 7, 9], [2, 3, 4, 5, 6, 7, 8]]



>>>>>> Sum to 36 <<<<<<
[[1, 5, 6, 7, 8, 9], [2, 4, 6, 7, 8, 9], [3, 4, 5, 7, 8, 9]]
[[1, 2, 3, 6, 7, 8, 9], [1, 2, 4, 5, 7, 8, 9], [1, 3, 4, 5, 6, 8, 9], [2, 3, 4, 5, 6, 7, 9]]
[[1, 2, 3, 4, 5, 6, 7, 8]]



>>>>>> Sum to 37 <<<<<<
[[2, 5, 6, 7, 8, 9], [3, 4, 6, 7, 8, 9]]
[[1, 2, 4, 6, 7, 8, 9], [1, 3, 4, 5, 7, 8, 9], [2, 3, 4, 5, 6, 8, 9]]
[[1, 2, 3, 4, 5, 6, 7, 9]]



>>>>>> Sum to 38 <<<<<<
[[3, 5, 6, 7, 8, 9]]
[[1, 2, 5, 6, 7, 8, 9], [1, 3, 4, 6, 7, 8, 9], [2, 3, 4, 5, 7, 8, 9]]
[[1, 2, 3, 4, 5, 6, 8, 9]]



>>>>>> Sum to 39 <<<<<<
[[4, 5, 6, 7, 8, 9]]
[[1, 3, 5, 6, 7, 8, 9], [2, 3, 4, 6, 7, 8, 9]]
[[1, 2, 3, 4, 5, 7, 8, 9]]



>>>>>> Sum to 40 <<<<<<
[[1, 4, 5, 6, 7, 8, 9], [2, 3, 5, 6, 7, 8, 9]]
[[1, 2, 3, 4, 6, 7, 8, 9]]



>>>>>> Sum to 41 <<<<<<
[[2, 4, 5, 6, 7, 8, 9]]
[[1, 2, 3, 5, 6, 7, 8, 9]]



>>>>>> Sum to 42 <<<<<<
[[3, 4, 5, 6, 7, 8, 9]]
[[1, 2, 4, 5, 6, 7, 8, 9]]



>>>>>> Sum to 43 <<<<<<
[[1, 3, 4, 5, 6, 7, 8, 9]]



>>>>>> Sum to 44 <<<<<<
[[2, 3, 4, 5, 6, 7, 8, 9]]



>>>>>> Sum to 45 <<<<<<
[[1, 2, 3, 4, 5, 6, 7, 8, 9]]