Two approaches to print all permutations - returning versus passing through the “result” list I have noticed many 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. What is the downside of returning (is it less memory/time efficient)? Example - To print all possible permutations, what makes this solution inefficient vs the second one.

public List&lt;List&lt;Integer&gt;&gt; perm(int[] nums){
    List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;List&lt;Integer&gt;&gt;();
    if(nums.length == 0){
        result.add(new ArrayList&lt;Integer&gt;());
        return result;        
    }
    for(int i= 0;i&lt;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&lt;List&lt;Integer&gt;&gt; tmp = perm(remnums);

        for(List&lt;Integer&gt; t : tmp){
            t.add(0,first);

        }
        result.addAll(tmp);
    }
    return result;
}


2nd approach ---

public List&lt;List&lt;Integer&gt;&gt; permute(int[] nums) {
   List&lt;List&lt;Integer&gt;&gt; list = new ArrayList&lt;&gt;();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList&lt;&gt;(), nums);
   return list;
}

private void backtrack(List&lt;List&lt;Integer&gt;&gt; list, List&lt;Integer&gt; tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList&lt;&gt;(tempList));
   } else{
      for(int i = 0; i &lt; nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}
I think the question you are asking is:  Given a recursive algorithm, is there an inherent difference between diving deep and capturing a result at the deepest level of the recursion, vs. passing that result back up the chain to be captured at the shallowest level of recursion.

Inherently, there should not be much difference.

If we look specifically at your implementation though, there are big performance issues that far outweigh any difference in the method of recursion.

In your first code example, this operation is essentially an O(N^2) operation.

    int[] remnums = new int[nums.length-1];
    int j = 0;
    for(int cur : nums){
        if(cur != first){
            remnums[j] = cur;j++;
        }
    }


In each recursive call, you are copying the N items (and removing one), resulting in a total of N * N/2 copies.  (N/2) is the average number of items copied, as we copy N-1 items in the first level, and 1 item in the last level.

Then notice:

    for(List&lt;Integer&gt; t : tmp){
        t.add(0,first);
    }


Adding to the front of an ArrayList must shift everything else over.  So this is another O(n^2) operation.  (or is this actually n^3, given all of the lists?)

In the second code example, this is an O(n^2) operation:

   if(tempList.contains(nums[i])) continue; // element already exists, skip


This is an O(n) linear search, for each N.

So, (at least in this example) it's not the recursion that's a problem.  It's the choice of algorithm and data structures.