Java bitmask solution


  • 0
    Z

    I think small constraints in the problem statement is hint for using bit manipulation technique, in contrast to other Combination sum problems.

    public class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
             List<List<Integer>> res = new ArrayList<>();
             if(n == 0 || k == 0) return res;
             
             int max = 1<<10;
             int min = 2;
             for(int i = min;i<max;i++){
                 List<Integer> list = new ArrayList<>();
                 int sum = 0;
                 int sets = 0;
                 for(int j = 1;j<=9;j++){
                     if((1&i) != 0) break;
                     if(((1<<j)&i)!=0){
                         sets++;
                         sum+=j;
                         list.add(j);
                     }
                 }
                 if(sets == k && sum == n){
                     res.add(list);
                 }
             }
             return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.