My recursive solution, easy to understand


  • 3
    Q

    First, sort the candidates and remove duplicates, I did this with set using 2 line

    Second, call the depth-first-search function to generate the result. In the function, I marked the largest element has been used, and only attempt to use the same or larger element when doing recursive calls which makes the result meet the ordering restriction.

    my code:

    class Solution {
    public:
        void dfs(vector<int> &can, int t, vector<int> &cur, int k, vector<vector<int> > &res) {
            if(t == 0) {
                res.push_back(cur);
                return;
            }
            if(can[k] <= t) {
                for(int i = k; i < can.size() and can[i] <= t; i++) {
                    cur.push_back(can[i]);
                    dfs(can, t - can[i], cur, i, res);
                    cur.pop_back();
                }
            }
            
        }
        vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
            vector<vector<int> > res;
            if(candidates.size() == 0) return res;
            set<int> dedup(candidates.begin(), candidates.end());
            candidates = vector<int>(dedup.begin(), dedup.end());
            vector<int> tmp;
            dfs(candidates, target, tmp, 0, res);
            return res;
        }
    };

  • 0
    N
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    S

    inorder to delete duplicates, you can use sort , unique and resize method of vector


  • 0
    M

    not a good idea, using set is faster


Log in to reply
 

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