494. Target Sum

https://leetcode.com/problems/target-sum/description/
Solution 1. DP
    int findTargetSumWays(vector<int>& nums, int S) {
        int sm =accumulate(nums.begin(), nums.end(), 0);
        if(sm < S) return 0;
        int target = sm + S;
        if(target & 1) return 0;
        target >>= 1;
        vector<int> dp(sm+1, 0);
        dp[0] = 1;
        for(auto n:nums) {
            for(int i=sm; i>=0; i--) {
                if(dp[i]) {
                    dp[i+n] += dp[i];
                }
            }
        }
        return dp[target];
    }
Solution 2. A slower one.
    int findTargetSumWays(vector<int>& nums, int S) {
        int res = 0;
        target(nums, 0, S, res);
        return res;
    }
    void target(vector<int>& nums, int i, int S, int& res) {
        if(i==nums.size()) {
            if(S==0) res++;
            return;
        }
        target(nums, i+1, S+nums[i], res);
        target(nums, i+1, S-nums[i], res);
    }
Solution 3. A much slower one
    int findTargetSumWays(vector<int>& nums, int S) {
        unordered_map<int,int> mp;
        for(int i:nums) mp[i]++;
        vector<vector<int>> vv;
        for(auto &m: mp) {
            int q = m.first;
            int n = m.second;
            vector<int> v;
            for(int i=0; i<=n; i++) {
                v.push_back((n-2*i)*q);
            }
            vv.push_back(v);
        }
        int res = 0;
        target(vv, 0, S, 1, res);
        return res;
    }
    void target(vector<vector<int>> &vv, int i, int S, int cnt, int& res) {
        if(i == vv.size()) {
            if(S==0) res += cnt;
            return;
        }
        for(int j=0; j<vv[i].size(); j++) {
            int n = ncj(vv[i].size()-1, j);
            target(vv, i+1, S-vv[i][j], cnt*n, res);
        }
    }
    int ncj( int n, int k ) {
        if (k > n) return 0;
        if (k * 2 > n) k = n-k;
        if (k == 0) return 1;

        int result = n;
        for( int i = 2; i <= k; ++i ) {
            result *= (n-i+1);
            result /= i;
        }
        return result;
    }