Accepted java solution


  • 1
    Z
    • Iterate over all the numbers with n bits, that is, let's iterate over 0 <= i < 2^n and look at each i number as a combination. A combination (number) is valid if bit count equals k.
    • If count of 1bits equal k then add new list/combination to the result (each number in the new list/combination is derived from the position of the corresponding 1 bit)
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            long num = 1 << n;
            for (int i=0; i<num; i++) {
                int curr = i;
                int bit1Count = 0;
                while (curr > 0) {
                    bit1Count++;
                    curr = curr & curr-1;
                    if (bit1Count > k) {
                        break;
                    }
                }
            
                if (bit1Count == k) {
                    add(n, i, res);    
                }
            
            }
            return res;   
        }
    
        private void add(int n, int curr, List<List<Integer>> res) {
            List<Integer> l = new LinkedList<>();
            for (int b=0; b<n; b++) {
                if (((curr >> b) & 1) == 1){
                    l.add(b+1);
                }
            }
            res.add(l);
        }

  • 0
    L

    Awesome! I think your idea can combine DP to get faster result. Actually you tried every possible combinations. If using DP. you don't need to worry about these impossible combinations.


Log in to reply
 

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