[LeetCode] Combination Sum 2
程序员文章站
2022-04-25 20:25:47
...
Question
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(
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环境执行报错 RecursionError: maximum recursion depth exceeded while calling a Python object
推荐阅读
-
LeetCode 15: 3Sum题解(python)
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
LeetCode - 1. Two Sum(8ms)
-
LeetCode_#1_两数之和 Two Sum_C++题解
-
259 [LeetCode] 3Sum Smaller 三数之和较小值
-
LeetCode(62)-Two Sum
-
LeetCode:Two Sum浅析
-
leetcode 2. Add Two Numbers
-
[LeetCode] 1. Two Sum 两数之和
-
Leetcode231. 2的幂