My O((n-k)*k) algorithm with O(n-k) space.


  • 0
    L

    DP solution is simple, how can we get combine(n, k)? It's two parts, one part is all the elements without number n(combine(n - 1, k), and another part is all the elements with number n (append n to every element of combine(n - 1, k - 1)). We can use a two dimension array to do it. Its row number is k, column number is n. So array[i, j] stand for combine(j, i). Actually, to get combine(n, k), we only need some elements in the array, because all element array[i, j] = empty when i > i. and combine(n, k) only need combine(n - 1, k - 1). So the area we need is a parallelogram.

    public class Solution
    {
        public List<List<Integer>> combine(int n, int k)
        {
            List<List<Integer>> result = new ArrayList<>();
            
            if (k <= n)
            {
                List<List<Integer>>[] previous = (List<List<Integer>>[]) new List[n - k + 2];
                List<List<Integer>>[] current = (List<List<Integer>>[]) new List[n - k + 2];
    
               // First row is combine(n, 0). every element is empty.
                for (int i = 0; i < previous.length; ++i)
                {
                    previous[i] = Collections.singletonList(Collections.<Integer>emptyList());
                }
                
                for (int i = 1; i <= k; ++i)
                {
                   // This one is combine(k - 1, k), it doesn't have any solution, so a empty list.
                    current[0] = Collections.<List<Integer>>emptyList();
                    
                    for (int j = 1; j < current.length; ++j)
                    {
                        // One part of combine(k, i) is combine(k - 1, i), don't use the new element k.
                        current[j] = new ArrayList<>(current[j - 1]);
                        
                        // Other part of combine(k, i) is with new element k, so it's every element of  combine(k - 1, i - 1) append k.
                        for (final List<Integer> list : previous[j])
                        {
                            final List<Integer> item = new ArrayList<>(list);
                            item.add(j + i - 1);
                            current[j].add(item);
                        }
                    }
                    final List<List<Integer>>[] temp = previous;
                    previous = current;
                    current = previous;
                }
                
                result = previous[previous.length - 1];
            }
            
            return result;
        }
    }

Log in to reply
 

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