recursion approach in java, solution can be applied to many other similar problem with minor modification


  • 0
    M
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            
            List<List<Integer>> res =new ArrayList<>();
            Integer[] temp = new Integer[k];
            int[] count = new int[n];
            Arrays.fill(count,1);
            find_combine(n,k,res,0, temp, count);
            
            return res;
            
        }
        
        public void find_combine(int n,int k,List<List<Integer>> res, int level, Integer[] temp, int[] count){
            
            if(level==k){
            	List<Integer> new_temp = new ArrayList<>();
            	for(int num: temp){
            		new_temp.add(num);
            	}
                res.add(new_temp);
                return;
            }
            
            for(int i=1; i<=n; i++){
                if(count[i-1]==0 || (temp[level]!=null && level-1>=0 && temp[level-1]>i))
                    continue;
                temp[level]=i;
                count[i-1]--;
                find_combine(n,k,res, level+1, temp, count);
                count[i-1]++;
            }
        
        }
    }
    

Log in to reply
 

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