LeetCode - 216. Combination Sum III

Question

题目

解析

这题其实也挺简单的，还是组合数的模板稍微改动一下。只不过将枚举数组中的元素改成 for(int i = cur; i <= 9; i++){ ，即枚举
cur ~ 9 ，而 cur 一开始自然是从 1 开始的。

import java.io.*;
import java.util.*;

class Solution {

    private List<List<Integer>> res;

    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        dfs(0, k, 1, 0, n, new ArrayList<>());// d is depth 
        return res;
    }

    private void dfs(int d, int k, int cur, int curSum, int target, List<Integer>curr){ 
        if(d == k){
            if(curSum == target)
                res.add(new ArrayList<>(curr));
            return;
        }
        for(int i = cur; i <= 9; i++){ 
            if(curSum + i > target)
                break;
            curr.add(i);
            dfs(d + 1, k, i + 1, curSum + i, target, curr);
            curr.remove(curr.size() - 1);
        }
    }

    public static void main(String[] args){
        PrintStream out = System.out;
        int k = 3, n = 9;
        out.println(new Solution().
            combinationSum3(3, 9)
        );
    }
}

因为这里的数只从 1 ~ 9 ，所以这题还有一种做法就是利用二进制枚举 2 ^ 9 种可能。

• 其中如果二进制（总共 9 位) 某位 i 上值为 1 ，则说明取了 i+1(因为二进制位数从 0 开始，但是这里是 1~9 (即从 1 开始))；如果 i 位置上为 0 ，则没有取 i+1 ；
• 枚举所有的二进制数( 0 ~ 2^9 )，然后每个数，对应哪些位置上是有数的（值为 1 )，如果有，就累加，最后看是不是等于 n 即可；

例如:

二进制( 0 ~ 2^9 )	对应集合
000000000	[ ]
000000001	[ 1 ]
000100011	[ 1, 2, 6]
010101101	[ 1, 3, 4, 6, 8]
111111110	[ 2, 3, 4, 5, 6, 7, 8, 9]
111111111	[1, 2, 3, 4, 5, 6, 7, 8, 9]

import java.io.*;
import java.util.*;

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();

        for(int mask = 0; mask < (1 << 9); mask++){ 
            List<Integer>cur = new ArrayList<>();
            int sum = 0;
            for(int i = 1; i <= 9; i++)
                // if( (mask & (1 << (i-1))) != 0){ 
                if( (( mask >> (i-1) ) & 1) == 1){// same as above
                    sum += i;
                    cur.add(i);
                }
            if(sum == n && cur.size() == k)
                res.add(new ArrayList<>(cur));
        }
        return res;
    }

    public static void main(String[] args){
        PrintStream out = System.out;
        int k = 3, n = 9;
        out.println(new Solution().
            combinationSum3(3, 9)
        );
    }
}