Leetcode 216 组合总和 III

题意理解：

        求数字1-9，任取k个数，其和为n的组合

        每个数字只能用一遍

        这里的求的是组合，即k个值不看顺序。

解题思路：按照回溯法解题模板

        1.确定返回值及参数

                List<>results :记录符合条件的结果

                path：用来记录k个数的组合

                //sum当前path里的值的和

                //startIndex指示之前没用过的数值作为新起点

                void backtracking(n,k,sum,startIndex)

        2.确定终止条件

                当且仅当sum==n时，找到结果，result.add(path) return;

                //此时可以又一个剪枝操作，sum>n时，即可剪枝。 return;

        3.单层逻辑

        for(int i=startIndex;i<=9;i++){//这里也可以进行剪枝，当当前startIndex指向的位置不足以取k个数时，剪枝。

                i<9-（k-path.size()）+1

                path.push(i);

                sum+=i;

                backtracking(n,k,sum,i+1);

                //回溯：

                sum-=i

                path.pop();

        }

1.暴力回溯+三个位置的剪枝

剪枝1：剪掉sum>n的

剪枝2：剪掉path.size组合数>k的

剪枝3：剪掉不足以凑出k个数组合的

List<List<Integer>> results=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k,n,0,1);
        return results;
    }
    public void backtracking(int k,int n,int sum,int startIndex){
        //终止条件
        //剪枝1:剪枝值超过n的
        if(sum>n) return;
        //剪枝2：超过k个数的组合
        else if (path.size()>k) return;
        else if (sum==n&&path.size()==k) {
            results.add(new ArrayList<>(path));
            return;
        }
        //单层逻辑:剪枝3：不能保证k个数
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            path.add(i);
            sum+=i;
            backtracking(k,n,sum,i+1);
            path.removeLast();
            sum-=i;
        }
 
    }

2.代码可优化的地方

//单层逻辑:剪枝1：不能保证k个数
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            path.add(i);
            sum+=i;
            backtracking(k,n,sum,i+1);
            path.removeLast();
            sum-=i;
        }
 
----------------------------------------------------------------
优化：
//单层逻辑:剪枝3：不能保证k个数
        for(int i=startIndex;i<=9-(k-path.size())+1;i++){
            path.add(i);
            backtracking(k,n,sum+i,i+1);
            path.removeLast();
        }

3.分析

时间复杂度：O(m×2^m)

空间复杂度：O(m)

m为集合大小