Returning versus pass-through


  • 0
    G

    I have noticed most of the backtracking problems have two ways of solving.

    One is to return "whatever's the required list",vs passing-through the "result" to every call and appending to it.
    Whats is the downside of returning .(Is it less memory/time efficient) ?
    Example - for permutation problem what makes this solution inefficient

    public List<List<Integer>> permute(int[] nums) {
    return perm(nums);
    }

    public List<List<Integer>> perm(int[] nums){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums.length == 0){
            result.add(new ArrayList<Integer>());
            return result;        
        }
        for(int i= 0;i<nums.length;i++){
            int first = nums[i];
            int[] remnums = new int[nums.length-1];
            int j = 0;
            for(int cur : nums){
                if(cur != first){
                    remnums[j] = cur;j++;
                }
            }
            List<List<Integer>> tmp = perm(remnums);
            
            for(List<Integer> t : tmp){
                t.add(0,first);
                
            }
            result.addAll(tmp);
        }
        return result;
    }

Log in to reply
 

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