# C++ Non-recursive, non-duplicate, DP solution (rare for this problem)

• Couldn't find a post with a proper DP solution for this problem. Almost everyone is using simple recursive.
Not a fan of recursive. Haven't employed any recursive to solve leetcode problems, and don't plan to.
Here even with DP we do not generate duplicate combinations in the first place.

``````class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> dp[target+1];
dp[0].push_back({});
for (int i = candidates.size()-1, p = 0; i >= 0; i--) {
int d = candidates[i] == p ? d + 1 : 0;
p = candidates[i];
for (int j = target; j >= p; j--) {
for (int k = j - p, m = dp[k].size()-1; m >= 0; m--) {
if (d && (dp[k][m].size() < d || *(dp[k][m].end()-d) != p)) continue;
dp[j].push_back(dp[k][m]);
dp[j].rbegin()->push_back(p);
}
}
}
return dp[target];
}
};
``````

• @ayuanx Please could you explain the logic?

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