Java - Pascals Rule - Recursive straightforward


  • 1
    D

    Reference
    https://en.wikipedia.org/wiki/Pascal's_rule

    Because Pascals rule is so clean. I wanted a solution similar.
    The idea is that when we get to the base case, we have either n == k or k == 0.

    In the case that k == 0, there is only 1 way to select 0 items out of n numbers, which is an empty list.

    In the case that n == k, there is only 1 way to select n items out of n numbers, which is to select them all.

    As for the recursive case building. Pascals Rule tells us that the number of ways to select k items out of n items is equal to the number of ways to select k items out of (n-1) items plus the number of ways to select (k-1) items out of (n-1) items. So this means we just need to add the kth number to the set that didn't include it.

    This isn't the fastest solution by any means.

    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            // Pascal's Identity (n,k) = (n-1,k) + (n-1,k-1). All previous that don't include the new one, and all previous that do include.
            List<List<Integer>> res = new ArrayList<>();
            
            if (k == 0) {
            	res.add(new ArrayList<Integer>());
                return res;
            } else if (n == k) {
            	
            	List<Integer> all = new ArrayList<>();
            	for (int i = 1; i <= n; i++) {
            		all.add(i);
            	}
            	
            	res.add(all);
            	return res;
            }
            
            List<List<Integer>> prevWith    = combine(n - 1, k);
            
            List<List<Integer>> prevWithout = combine(n - 1, k - 1);
            for (List<Integer> prev : prevWithout) {
            	prev.add(n);
            }
            
            res.addAll(prevWith);
            res.addAll(prevWithout);
            
            return res;
        }
    }
    

Log in to reply
 

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