5
\$\begingroup\$

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<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;
}

2nd approach ---

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

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < 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);
      }
   }
} 
\$\endgroup\$
3
+25
\$\begingroup\$

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<Integer> 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.

\$\endgroup\$
  • \$\begingroup\$ I am more concerned about whether returning "List<List<Integer>> " is better or passing it through.The difference in the piece of code you mentioned is accidental and it can be made similar for both the programs.I am more concerned about the time-complexity assuming everything else is similar. \$\endgroup\$ – code4fun Oct 4 '17 at 7:01
  • \$\begingroup\$ My point is that, given your example, any small differences in the recursion method would be completely overshadowed by the huge, algorithmic issues. Maybe you can simplify the problem down to basics - like calculating factorial(n) - and then we can focus on the recursion rather than the algorithm. You're trying to compare the weight of 2 different elephants, one with a flea on it's back. We need to eliminate the elephants so that we can weigh the flea. \$\endgroup\$ – JimB Oct 4 '17 at 17:22
1
\$\begingroup\$

This question is about recursion vs looping over a dataset to calculate the results. In general looping is more efficient than recursive function calls, as the calls come with overhead. There are some exceptions to that. See here for more details. https://stackoverflow.com/questions/15688019/recursion-versus-iteration

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.