Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf3cc142

Browse files
authored
Merge pull requestneetcode-gh#3682 from Srihari2222/develop_articles
Sri Hari: Batch-2/Neetcode-150/articles
2 parents80a12e6 +3b1a8d5 commitf3cc142

File tree

5 files changed

+2383
-0
lines changed

5 files changed

+2383
-0
lines changed

‎articles/combination-target-sum.md

Lines changed: 306 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,306 @@
1+
##1. Backtracking
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defcombinationSum(self,nums: List[int],target:int) -> List[List[int]]:
8+
res= []
9+
10+
defdfs(i,cur,total):
11+
if total== target:
12+
res.append(cur.copy())
13+
return
14+
if i>=len(nums)or total> target:
15+
return
16+
17+
cur.append(nums[i])
18+
dfs(i, cur, total+ nums[i])
19+
cur.pop()
20+
dfs(i+1, cur, total)
21+
22+
dfs(0, [],0)
23+
return res
24+
```
25+
26+
```java
27+
publicclassSolution {
28+
List<List<Integer>> res;
29+
publicList<List<Integer>>combinationSum(int[]nums,inttarget) {
30+
res=newArrayList<List<Integer>>();
31+
List<Integer> cur=newArrayList();
32+
backtrack(nums, target, cur,0);
33+
return res;
34+
}
35+
36+
publicvoidbacktrack(int[]nums,inttarget,List<Integer>cur,inti) {
37+
if (target==0) {
38+
res.add(newArrayList(cur));
39+
return;
40+
}
41+
if (target<0|| i>= nums.length) {
42+
return;
43+
}
44+
45+
cur.add(nums[i]);
46+
backtrack(nums, target- nums[i], cur, i);
47+
cur.remove(cur.size()-1);
48+
backtrack(nums, target, cur, i+1);
49+
}
50+
}
51+
```
52+
53+
```cpp
54+
classSolution {
55+
public:
56+
vector<vector<int>> res;
57+
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
58+
vector<int> cur;
59+
backtrack(nums, target, cur, 0);
60+
return res;
61+
}
62+
63+
void backtrack(vector<int>& nums, int target, vector<int>& cur, int i) {
64+
if (target == 0) {
65+
res.push_back(cur);
66+
return;
67+
}
68+
if (target <0 || i >= nums.size()) {
69+
return;
70+
}
71+
72+
cur.push_back(nums[i]);
73+
backtrack(nums, target - nums[i], cur, i);
74+
cur.pop_back();
75+
backtrack(nums, target, cur, i + 1);
76+
}
77+
};
78+
```
79+
80+
```javascript
81+
classSolution {
82+
/**
83+
*@param{number[]}nums
84+
*@param{number}target
85+
*@returns{number[][]}
86+
*/
87+
combinationSum(nums,target) {
88+
let ans= [];
89+
let cur= [];
90+
this.backtrack(nums, target, ans, cur,0);
91+
return ans;
92+
}
93+
94+
/**
95+
*@param{number[]}nums
96+
*@param{number}target
97+
*@param{number[][]}ans
98+
*@param{number[]}cur
99+
*@param{number}index
100+
*/
101+
backtrack(nums,target,ans,cur,index) {
102+
if (target===0) {
103+
ans.push([...cur]);
104+
}elseif (target<0|| index>=nums.length) {
105+
return;
106+
}else {
107+
cur.push(nums[index]);
108+
this.backtrack(nums, target- nums[index], ans, cur, index);
109+
110+
cur.pop();
111+
this.backtrack(nums, target, ans, cur, index+1);
112+
}
113+
}
114+
}
115+
```
116+
117+
```csharp
118+
publicclassSolution {
119+
120+
List<List<int>>res=newList<List<int>>();
121+
122+
publicvoidbacktrack(inti,List<int>cur,inttotal,int[]nums,inttarget) {
123+
if(total==target) {
124+
res.Add(cur.ToList());
125+
return;
126+
}
127+
128+
if(total>target||i>=nums.Length)return;
129+
130+
cur.Add(nums[i]);
131+
backtrack(i,cur,total+nums[i],nums,target);
132+
cur.Remove(cur.Last());
133+
134+
backtrack(i+1,cur,total,nums,target);
135+
136+
}
137+
publicList<List<int>>CombinationSum(int[]nums,inttarget) {
138+
backtrack(0,newList<int>(),0,nums,target);
139+
returnres;
140+
}
141+
}
142+
```
143+
144+
::tabs-end
145+
146+
###Time & Space Complexity
147+
148+
* Time complexity: $O(2 ^ \frac{t}{m})$
149+
* Space complexity: $O(\frac{t}{m})$
150+
151+
>Where $t$ is the given $target$ and $m$ is the minimum value in $nums$.
152+
153+
---
154+
155+
##2. Backtracking (Optimal)
156+
157+
::tabs-start
158+
159+
```python
160+
classSolution:
161+
defcombinationSum(self,nums: List[int],target:int) -> List[List[int]]:
162+
res= []
163+
nums.sort()
164+
165+
defdfs(i,cur,total):
166+
if total== target:
167+
res.append(cur.copy())
168+
return
169+
170+
for jinrange(i,len(nums)):
171+
if total+ nums[j]> target:
172+
return
173+
cur.append(nums[j])
174+
dfs(j, cur, total+ nums[j])
175+
cur.pop()
176+
177+
dfs(0, [],0)
178+
return res
179+
```
180+
181+
```java
182+
publicclassSolution {
183+
List<List<Integer>> res;
184+
publicList<List<Integer>>combinationSum(int[]nums,inttarget) {
185+
res=newArrayList<>();
186+
Arrays.sort(nums);
187+
188+
dfs(0,newArrayList<>(),0, nums, target);
189+
return res;
190+
}
191+
192+
privatevoiddfs(inti,List<Integer>cur,inttotal,int[]nums,inttarget) {
193+
if (total== target) {
194+
res.add(newArrayList<>(cur));
195+
return;
196+
}
197+
198+
for (int j= i; j< nums.length; j++) {
199+
if (total+ nums[j]> target) {
200+
return;
201+
}
202+
cur.add(nums[j]);
203+
dfs(j, cur, total+ nums[j], nums, target);
204+
cur.remove(cur.size()-1);
205+
}
206+
}
207+
}
208+
```
209+
210+
```cpp
211+
classSolution {
212+
public:
213+
vector<vector<int>> res;
214+
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
215+
sort(nums.begin(), nums.end());
216+
dfs(0, {}, 0, nums, target);
217+
return res;
218+
}
219+
220+
void dfs(int i, vector<int> cur, int total, vector<int>& nums, int target) {
221+
if (total == target) {
222+
res.push_back(cur);
223+
return;
224+
}
225+
226+
for (int j = i; j < nums.size(); j++) {
227+
if (total + nums[j] > target) {
228+
return;
229+
}
230+
cur.push_back(nums[j]);
231+
dfs(j, cur, total + nums[j], nums, target);
232+
cur.pop_back();
233+
}
234+
}
235+
};
236+
```
237+
238+
```javascript
239+
classSolution {
240+
/**
241+
*@param{number[]}nums
242+
*@param{number}target
243+
*@returns{number[][]}
244+
*/
245+
combinationSum(nums,target) {
246+
constres= [];
247+
nums.sort((a,b)=> a- b);
248+
249+
constdfs= (i,cur,total)=> {
250+
if (total=== target) {
251+
res.push([...cur]);
252+
return;
253+
}
254+
255+
for (let j= i; j<nums.length; j++) {
256+
if (total+ nums[j]> target) {
257+
return;
258+
}
259+
cur.push(nums[j]);
260+
dfs(j, cur, total+ nums[j]);
261+
cur.pop();
262+
}
263+
};
264+
265+
dfs(0, [],0);
266+
return res;
267+
}
268+
}
269+
```
270+
271+
```csharp
272+
publicclassSolution {
273+
List<List<int>>res;
274+
publicList<List<int>>CombinationSum(int[]nums,inttarget) {
275+
res=newList<List<int>>();
276+
Array.Sort(nums);
277+
dfs(0,newList<int>(),0,nums,target);
278+
returnres;
279+
}
280+
281+
privatevoiddfs(inti,List<int>cur,inttotal,int[]nums,inttarget) {
282+
if (total==target) {
283+
res.Add(newList<int>(cur));
284+
return;
285+
}
286+
287+
for (intj=i;j<nums.Length;j++) {
288+
if (total+nums[j]>target) {
289+
return;
290+
}
291+
cur.Add(nums[j]);
292+
dfs(j,cur,total+nums[j],nums,target);
293+
cur.RemoveAt(cur.Count-1);
294+
}
295+
}
296+
}
297+
```
298+
299+
::tabs-end
300+
301+
###Time & Space Complexity
302+
303+
* Time complexity: $O(2 ^ \frac{t}{m})$
304+
* Space complexity: $O(\frac{t}{m})$
305+
306+
>Where $t$ is the given $target$ and $m$ is the minimum value in $nums$.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp