Clean 0ms DFS and backtracking C++ solution


  • 2
    C

    This problem can be rephrased into the following, given an input array consists of numbers from 1 to 9, find its subset of size k which sums to sum n.

    Naturally we can have a DFS solution to solve it with O(2^9). At each level indicated by the current value we need to pick or skip, we will branch into two cases: include this number or skip this number.

    Thus the solution is very straightforward:

        vector<vector<int>> combinationSum3(int k, int n) {
            vector<int> path;
            vector<vector<int>> result;
            combinations(1, k, n, path, result);
            return result;
        }
        
        void combinations(int current, int k, int n, vector<int>& path, vector<vector<int>>& result) {
            if (path.size() == k) {
                if (n == 0) result.push_back(path);
                return;
            }
            if (current > 9) return;
            
            /* do not add current */
            combinations(current+1, k, n, path, result);
            
            path.push_back(current);
            combinations(current+1, k, n-current, path, result);
            path.pop_back();
        }
    

Log in to reply
 

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