DFS + backtracking


  • 0
    N

    Time complexity : ??, I could not figure it out

    Running Time: Beat 78.99%

    Code
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> combination;
    vector<vector<int>> combinations;
    recursion(0, candidates, target, combination, combinations);
    return combinations;
    }

    void recursion(int k, vector<int>& candidates, int target, vector<int>&combination, vector<vector<int>>& combinations) {
        if (target < 0) {
            return;
        }
        
        if(target == 0) {
            combinations.push_back(combination);
            return;
        }
        
        for(int i = k; i < candidates.size(); i++) {
            combination.push_back(candidates[i]);
            recursion(i, candidates, target - candidates[i], combination, combinations);
            combination.pop_back();
    
        }
    }
    

    Algorithm:
    This is a typical combinatorial search problem. dfs-based backtracking is the straightforward solution.
    As this is DFS, we should module the problem into graph, which means defining the vertex and neighbors. suppose a vertex is a combination [i1, i2,..., i k-1, ik] ( 0<=i1<=i2<=..<=i k-1 <= ik <= len(array)), so its neighbors would be [i1, i2,..,i k -1, ik, ik+1]. So the graph would be a unweighted and undirected grpah, empty set is the root. our goal is to find qualified vertex which can sum up to k.
    suppose we are given a array [1, 2]. and the tree would be [ [ ], [1], [2], [1,1], [1,2], [2,2], [1,1,1], [1,1,2],[1,2,2], [2,2,2].... ], represented in a serialization tree

    I'd appreciate that If anyone can help to figure out the time complexity,


Log in to reply
 

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