My Java Accepted Solution using recursive call


  • 0
    S

    The idea is a combine(n,k) is made up of i+combine(n-i,k-1) (+i for each element in combine(n-i,k-1)), for i from 1 to n.

    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> output = new ArrayList<List<Integer>>();
            // base case
            if(k == 0 || n == 0){return output;}
            if(k == 1){
                for(int i = 1;i <= n;i++){
                    List<Integer> lst = new ArrayList<Integer>();
                    lst.add(i);
                    output.add(lst);
                }
                return output;
            }
            
            // recursive
            for(int i = 1;i <= n;i++){
                List<List<Integer>> lst = combine(n-i,k-1);
                // add offset i to each
                for(int x = 0;x < lst.size();x++){
                    lst.get(x).add(0,i);
                    for(int y = 1;y < lst.get(x).size();y++)
                        lst.get(x).set(y,lst.get(x).get(y)+i);
                }
                
                output.addAll(lst);
            }
            
            return output;
            
        }
    

    }


  • 0
    L

    Mine:

    public class Solution
    {
        public List<List<Integer>> combine(int n, int k)
        {
            if (n < k)
            {
                return Collections.<List<Integer>>emptyList();
            }
            else if (k == 0)
            {
                return Collections.singletonList(Collections.<Integer>emptyList());
            }
            else
            {
                final List<List<Integer>> result = new ArrayList<>();
                for (int i = k; i <= n; ++i)
                {
                    for (final List<Integer> list : combine(i - 1, k - 1))
                    {
                        final List<Integer> item = new ArrayList<>(list);
                        item.add(i);
                        result.add(item);
                    }
                }
                
                return result;
            }
        }
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


Log in to reply
 

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