3 ms Java Solution


  • 13
    A
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (k > n || k < 0) {
                return result;
            }
            if (k == 0) {
                result.add(new ArrayList<Integer>());
                return result;
            }
            result = combine(n - 1, k - 1);
            for (List<Integer> list : result) {
                list.add(n);
            }
            result.addAll(combine(n - 1, k));
            return result;
        }
    }

  • 0
    Z

    very short! amazing. indeed.


  • 0
    Y

    some kind of DP, great performance


  • 0
    K

    Thank you very much for sharing with us this amazing solution! and I further improved the code to make it more concise, explanation included in the comment

    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> ans = new LinkedList();
            if (n < k || k == 0) return ans;
    
            ans = combine(n-1, k-1);
            //if at this point ans is empty, it can only be that k-1 == 0, 
            //n-1<k-1 is not possible since n>=k (if n<k, the function would have already returned at an early point)
            if (ans.isEmpty()) ans.add(new LinkedList<Integer>());
            for (List<Integer> list:ans) list.add(n);
            
            ans.addAll(combine(n-1, k));
            return ans;
        }
    }
    

Log in to reply
 

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