[TargetSum] 求问下哪些递归属于回溯

1. public int findTargetSumWays(int[] nums, int S) {
   
2.     if (nums == null || nums.length == 0){
   
3.       return 0;
   
4.     }
   
5.     return helper(nums, 0, 0, S, new HashMap<>());
   
6.   }
   
7.   private int helper(int[] nums, int index, int sum, int S, Map<String, Integer> map){
   
8.     String encodeString = index + "->" + sum;
   
9.     if (map.containsKey(encodeString)){
   
10.       return map.get(encodeString);
    
11.     }
    
12.     if (index == nums.length){
    
13.       if (sum == S){
    
14.         return 1;
    
15.       }else {
    
16.         return 0;
    
17.       }
    
18.     }
    
19.     int curNum = nums[index];
    
20.     int add = helper(nums, index + 1, sum - curNum, S, map);
    
21.     int minus = helper(nums, index + 1, sum + curNum, S, map);
    
22.     map.put(encodeString, add + minus);
    
23.     return add + minus;
    
24.   }

复制代码

这题用DFS做，为什么不需要回溯呢？比如下面这个例子，明显是一直回溯到第一个+号，后面再递归的吧
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3