'Backtrack the difference between these two codes
I have been trying to play around with backtracking. From my understanding these two codes are doing same thing but somehow I got different outcomes.
I am just trying to use some type of template to start with.
cout<<i<<endl;
backtrack(i+1);
backtrack(i+1);
and
for(int i=start; i<n; i++){
cout<<i<<endl;
backtrack(i+1);
}
The first one gets 5 as outcome and the second one gets six when I have the input of nums=[1,1,1,1,1] target = 3
public class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
calculate(nums, 0, 0, S);
return count;
}
public void calculate(int[] nums, int i, int sum, int S) {
if (i == nums.length) {
if (sum == S) {
count++;
}
} else {
calculate(nums, i + 1, sum + nums[i], S);
calculate(nums, i + 1, sum - nums[i], S);
}
}
}
class Solution {
public:
int count;
void backtrack(vector<int>& nums, int target, int start, int sum){
if(start==nums.size()){
if(sum==target){
count++;
}
return;
}
else{
for(int i=start; i<nums.size(); i++){
//sum+=nums[i];
backtrack(nums, target, i+1, sum+nums[i]);
sum-=nums[i];
}
}
}
int findTargetSumWays(vector<int>& nums, int target) {
count=0;
int sum=0;
int total=0;
for(auto x:nums)total+=x;
vector<vector<int>> dp;
backtrack(nums, target, 0, sum);
return count;
}
};
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
