Java solution with algorithmic approach for this kind of problem


  • 0
    L

    If by looking at this question, you can realize you need a recursive approach but not quite sure how, read on. The idea is that you are trying to build a series of stacks where you could iterate over all the numbers at the top stack but only the numbers that come after that in the subsequent stacks. For example, you may realize that what you are looking for is:

    //for i in 1...n
    //add i and then in the next stack select what comes after i
    //now try another value of i till n

    /**
    Algorithm:
    Run a loop of 1..n numbers. Push the number in a list.
    Go to the next stack and pick another number. When the size
    of the list is k, come back to try another combination.Like,
    for i in 1...n
    set.add(i)
    dfs(n,list);
    set.remove(i)
    The loop always run in one direction meaning that we start from
    start to n and slowing decrease the range for future stacks.
    */

        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> ll = new ArrayList<>();
            List<Integer> l = new ArrayList<>();
            helper(1,n,k,ll,l);
            return ll;
        }
        
        private void helper(int s, int n, int k, List<List<Integer>> ll, List<Integer> l) {
            if(l.size()==k) {
                ll.add(new ArrayList<Integer>(l));
                return;
            }
            
            for(int i=s;i<=n;i++) {
                l.add(i);
                helper(i+1,n,k,ll,l);
                l.remove(l.size()-1);            
            }        
        } 
    

Log in to reply
 

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