欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[LeetCode] Combination Sum 2

程序员文章站 2022-04-25 20:25:47
...

Question

[LeetCode] Combination Sum 2

Analysis

This question is similar to the question Path Sum 2 and Two Sum. I choose recursion to solve it, just like Path Sum 2.
The main idea is easy, but an important question is how to eliminate duplicate.It’s the difficultest part of this question. I use the idea that it cannot appear the same value at the same index(the relative position of the array ). I just need to add an condition sentence before entering recursive sentence.

The analysis of the time complexity

Exactly, I use the idea of dfs, but I am not sure about it’s time complexity. I think it’s O(n2).

Code

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        can = candidates;
        size = candidates.size();
        vector<int> temp;
        for (int i = 0; i < size; i++) {
            if (i > 0 && can[i -1] == can[i]) continue;
            findOneAnswer(temp, i, target);
        }
        return ans;
    }
    void findOneAnswer(vector<int> & v, int index, int target) {
        if (can[index] > target) return;
        v.push_back(can[index]);
        if (target - can[index] == 0) {
            ans.push_back(v);
            v.pop_back();
            return;
        }
        for (int i = index + 1; i < size; i++) {
            if (i > index + 1 && can[i -1] == can[i]) continue;
            findOneAnswer(v, i, target - can[index]);
        }
        v.pop_back();
    }
    vector<vector<int> > ans;
    vector<int> can;
    int size;
};
相关标签: leetcode recursion