Concise Backtracking Solution


  • 20
    V

    We backtrack from successful searches as well because they are saved at the leafs of recursion tree

    class Solution {
    public:
    
        void search(vector<int>& num, int next, vector<int>& pSol, int target, vector<vector<int> >& result)
        {
            if(target == 0)
            {
                result.push_back(pSol);
                return;
            }
            
            if(next == num.size() || target - num[next] < 0)
                return;
                
            pSol.push_back(num[next]);
            search(num, next, pSol, target - num[next], result);
            pSol.pop_back();
            
            search(num, next + 1, pSol, target, result);
        }
    
        
        vector<vector<int> > combinationSum(vector<int> &num, int target) 
        {
            vector<vector<int> > result;
            sort(num.begin(), num.end());
            vector<int> pSol;
            search(num, 0, pSol, target, result);
            return result;    
        }
    };

  • 0
    K
    This post is deleted!

  • 0
    J

    Concise solution.

    But a shortcoming of this solution is, that for the same number, it still increases call stack which is not necessary. This line:

    search(num, next, pSol, target - num[next], result);
    

    This can be replaced with a for-loop. Otherwise, for a input like candidates==[1] and target==10000, this solution will immediately have a 10000 level call stack, which might exceed OS's tolerance.

    What do you think?


  • 0
    W

    what if the input is [2,2],4?


  • 0
    E

    Here is my java backtracking solution,it's easy to understand.

    public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> sets = new ArrayList<List<Integer>>();
        backTrack(sets,new ArrayList<Integer>(),candidates,0,target,candidates.length-1);
        return sets;
    }
    public void backTrack(List<List<Integer>> sets,List<Integer> path,int[] nums,int sum,int target,int index){
        if(sum==target){
            sets.add(new ArrayList<Integer>(path));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=index;i>=0;i--){
            sum += nums[i];
            path.add(0,nums[i]);
            backTrack(sets,path,nums,sum,target,i);
            sum -= nums[i];
            path.remove(0);
        }
    }
    

    }


  • 0
    L

    I don't know how to replace this line with a for loop. Could you give me some hint? Thanks.


  • 0
    R

    similar backtracking solution

    void elementSum(vector<int>&candidates,vector<vector<int>>&res,vector<int>&elements,int target ,int begin){
            if(!target){
                res.push_back(elements); return;
            }
            for(int i=begin;i<candidates.size() && candidates[i] <= target ;i++){
                elements.push_back(candidates[i]);
                elementSum(candidates,res,elements,target-candidates[i],i);
                elements.pop_back();
            }
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<int>elements;
            vector<vector<int>> res;
            sort(candidates.begin(),candidates.end());
            elementSum(candidates,res,elements,target,0);
            return res;
        }

  • 0
    A

    @rakesh_joshi Hey Joshi, your code is great. I have a recursion related problem. I only see there is one "return" condition. What if there exist a situation where we can't find a vector the sum of which equals to target? Where does this code return?


Log in to reply
 

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