در این مطلب، ویدئو زیرمجموعه های II – Backtracking – Leetcode 90 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:16:08
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,000 –> 00:00:02,080
با استفاده از لینک موجود در توضیحات algomonster را بررسی کنید
2
00:00:02,080 –> 00:00:05,040
و از code neat برای
3
00:00:05,040 –> 00:00:08,160
10 دسترسی مادام العمر استفاده کنید سلام به همه خوش
4
00:00:08,160 –> 00:00:09,920
آمدید و بیایید امروز چند کد دقیق تر بنویسیم
5
00:00:09,920 –> 00:00:11,759
تا امروز
6
00:00:11,759 –> 00:00:14,880
زیرمجموعه های مشکل 2 را حل کنیم. ما اولین مورد از
7
00:00:14,880 –> 00:00:16,560
این و آن را حل کردیم در واقع خیلی وقت
8
00:00:16,560 –> 00:00:18,080
پیش و مردم درخواست کردند که من
9
00:00:18,080 –> 00:00:20,000
این مورد را نیز حل کردم، بنابراین بیایید امروز آن را انجام دهیم
10
00:00:20,000 –> 00:00:22,160
اولین مورد در واقع بسیار
11
00:00:22,160 –> 00:00:24,400
شبیه به این یکی است، تنها تفاوت
12
00:00:24,400 –> 00:00:27,359
این است که در این مورد آرایه ورودی
13
00:00:27,359 –> 00:00:29,519
که به ما داده می شود می تواند حاوی مقداری باشد.
14
00:00:29,519 –> 00:00:32,159
مقادیر تکراری در حال حاضر کار ما
15
00:00:32,159 –> 00:00:34,960
هنوز یکسان است، میخواهیم تمام زیرمجموعههای ممکن را
16
00:00:34,960 –> 00:00:38,239
که میتوانیم از اعداد آرایه ورودی
17
00:00:38,239 –> 00:00:40,719
برگردانیم، اما از آنجایی که
18
00:00:40,719 –> 00:00:43,520
مقادیر تکراری داریم، برای
19
00:00:43,520 –> 00:00:47,039
ما مشکل است که هیچ زیرمجموعهای تکراری در
20
00:00:47,039 –> 00:00:49,200
نتیجه نداشته باشیم، نکته خوب این است که ما میتوانیم
21
00:00:49,200 –> 00:00:51,920
راهحل را به هر ترتیبی برگردانیم، بنابراین خوب است،
22
00:00:51,920 –> 00:00:53,760
اما بیایید به یک مثال نگاهی بیندازیم.
23
00:00:53,760 –> 00:00:56,879
24
00:00:56,879 –> 00:00:59,359
25
00:00:59,359 –> 00:01:02,000
26
00:01:02,000 –> 00:01:03,600
بنابراین می دانید که ما فقط می
27
00:01:03,600 –> 00:01:05,920
توانیم مقدار یک را بگیریم که یک زیرمجموعه است،
28
00:01:05,920 –> 00:01:08,240
می توانیم مقدار دوم را بگیریم
29
00:01:08,240 –> 00:01:10,799
که یک زیر مجموعه است و همچنین می توانیم
30
00:01:10,799 –> 00:01:13,680
مقدار سوم را به خودی خود بگیریم که آن هم
31
00:01:13,680 –> 00:01:15,920
دو است، اما در اینجا می توانید ببینید که ما یک مورد
32
00:01:15,920 –> 00:01:18,000
تکراری داریم. هر دو یکسان هستند،
33
00:01:18,000 –> 00:01:20,159
نمیتوانیم هر دوی آنها را بگنجانیم، بنابراین
34
00:01:20,159 –> 00:01:21,920
میدانید که ما دومی را در نظر نمیگیریم
35
00:01:21,920 –> 00:01:24,000
و اتفاقاً حتی اگر هیچکدام از اینها را انتخاب نکنیم،
36
00:01:24,000 –> 00:01:26,159
مثلاً اگر فقط یک
37
00:01:26,159 –> 00:01:27,439
لیست خالی داشته
38
00:01:27,439 –> 00:01:30,479
باشیم که هنوز یک لیست است. همانطور که
39
00:01:30,479 –> 00:01:32,880
در خروجی اینجا مشاهده می کنید، ما
40
00:01:32,880 –> 00:01:35,119
همچنین می توانیم اولین زیرمجموعه را بگیریم و
41
00:01:35,119 –> 00:01:37,759
دو مورد اول را بگیریم که به ما یک دو
42
00:01:37,759 –> 00:01:39,360
می دهد، می توانیم اولین را بگیریم و
43
00:01:39,360 –> 00:01:41,360
سپس دو دوم را بگیریم، اما این
44
00:01:41,360 –> 00:01:43,119
دقیقاً همان است که یکی دو نیز
45
00:01:43,119 –> 00:01:44,960
باشید تا هر دوی آن ها را حفظ نکنیم،
46
00:01:44,960 –> 00:01:46,720
بنابراین شما شروع به درک این ایده
47
00:01:46,720 –> 00:01:48,960
می کنید که زیر مجموعه ها را به طور کلی می شناسید و
48
00:01:48,960 –> 00:01:50,799
مشکل اینجاست که ما
49
00:01:50,799 –> 00:01:53,040
هیچ تکراری را در نتایج خود لحاظ نکنیم.
50
00:01:53,040 –> 00:01:54,720
هنگامی که ما هیچ
51
00:01:54,720 –> 00:01:56,880
تکراری را شامل نمیشویم، شش زیر مجموعه مختلف
52
00:01:56,880 –> 00:01:58,640
داریم که داریم می توانید ایجاد کنید و قبل از اینکه ما
53
00:01:58,640 –> 00:02:00,159
واقعاً وارد این ادعا شویم،
54
00:02:00,159 –> 00:02:01,920
ممکن است فکر کنید خوب است، شاید
55
00:02:01,920 –> 00:02:03,840
برنامه نویسی پویا کاری باشد که ما می توانیم انجام دهیم و
56
00:02:03,840 –> 00:02:06,320
ممکن است، اما من
57
00:02:06,320 –> 00:02:07,840
بلافاصله با بررسی این مشکل
58
00:02:07,840 –> 00:02:10,160
می دانم که ما نمی توانیم برنامه نویسی پویا انجام دهیم
59
00:02:10,160 –> 00:02:11,599
و دلیل آن این است که ما واقعاً
60
00:02:11,599 –> 00:02:13,440
زیرمجموعهها یا هر چیز دیگری را نمیشماریم،
61
00:02:13,440 –> 00:02:16,319
ما در واقع زیرمجموعهها را ایجاد میکنیم، بنابراین
62
00:02:16,319 –> 00:02:18,640
حتی اگر نوعی میانبر پیدا
63
00:02:18,640 –> 00:02:20,319
کنیم، واقعاً کارآمدتر نمیشود،
64
00:02:20,319 –> 00:02:21,840
زیرا هنوز باید
65
00:02:21,840 –> 00:02:25,200
همه این زیرمجموعهها و چند تا را ایجاد کنیم.
66
00:02:25,200 –> 00:02:27,440
زیرمجموعههای ممکن را میتوانیم برای
67
00:02:27,440 –> 00:02:30,160
تولید زیرمجموعهای برای هر مقدار داشته باشیم،
68
00:02:30,160 –> 00:02:32,160
میتوانیم انتخاب کنیم که این مقدار را شامل شود یا
69
00:02:32,160 –> 00:02:34,239
آن مقدار را شامل نشود، بنابراین برای هر مقدار
70
00:02:34,239 –> 00:02:36,319
دو انتخاب داریم، حالا چند مقدار
71
00:02:36,319 –> 00:02:37,920
در ورودی خود داریم، بگذارید
72
00:02:37,920 –> 00:02:40,400
آن را n بنامیم. فرض کنید 2 به توان n
73
00:02:40,400 –> 00:02:43,040
چند زیرمجموعه داریم که
74
00:02:43,040 –> 00:02:45,519
اکنون هر زیرمجموعه باید
75
00:02:45,519 –> 00:02:47,440
حداکثر چقدر طول داشته باشد، طول آن می تواند n باشد، بنابراین
76
00:02:47,440 –> 00:02:48,959
تعداد زیر مجموعه ها را
77
00:02:48,959 –> 00:02:50,959
ضرب در t می کنیم. طول زیرمجموعه
78
00:02:50,959 –> 00:02:53,040
بنابراین این پیچیدگی کلی زمان
79
00:02:53,040 –> 00:02:55,360
برای تولید همه
80
00:02:55,360 –> 00:02:57,519
این زیرمجموعه ها خواهد بود، توجه داشته باشید که چگونه می توانیم
81
00:02:57,519 –> 00:02:59,120
این را بفهمیم حتی اگر
82
00:02:59,120 –> 00:03:01,280
هنوز مشکل را حل نکرده ایم و این نوع
83
00:03:01,280 –> 00:03:03,120
نکات به شما نشان می دهد که چگونه هستیم. برای حل
84
00:03:03,120 –> 00:03:05,120
این مشکل، این اساساً یک
85
00:03:05,120 –> 00:03:06,400
راه حل brute force است، بنابراین ما از بازگشت به
86
00:03:06,400 –> 00:03:08,640
عقب استفاده خواهیم کرد، بنابراین بیایید
87
00:03:08,640 –> 00:03:10,720
وارد آن شویم، بنابراین اجازه دهید نگاهی به یک
88
00:03:10,720 –> 00:03:12,640
مثال بیندازیم و اجازه دهید با
89
00:03:12,640 –> 00:03:14,800
راه حل زیر مجموعه اول شروع کنیم که در واقع
90
00:03:14,800 –> 00:03:16,800
بسیار پیش پا افتاده است. برای یک
91
00:03:16,800 –> 00:03:19,360
مشکل عقبگرد به یاد داشته باشید که ما می خواهیم هر
92
00:03:19,360 –> 00:03:21,360
زیر مجموعه ممکن را ایجاد کنیم، بنابراین برای هر یک
93
00:03:21,360 –> 00:03:23,120
از این مقادیر ورودی، یک
94
00:03:23,120 –> 00:03:25,360
انتخاب داریم که آیا این یکی را درج
95
00:03:25,360 –> 00:03:27,280
کنیم یا قرار نیست این یکی را وارد کنیم، بنابراین
96
00:03:27,280 –> 00:03:29,040
آن را با یک درخت تصمیم ساده تر بیان کنیم.
97
00:03:29,040 –> 00:03:31,120
شما می دانید برای اولین تصمیمی که
98
00:03:31,120 –> 00:03:33,519
داریم، ما در این مورد درست هستیم و می
99
00:03:33,519 –> 00:03:34,640
دانیم که چون
100
00:03:34,640 –> 00:03:36,400
یک شاخص را دنبال می کنیم، یک اشاره گر را هر طور که می خواهید
101
00:03:36,400 –> 00:03:38,159
آن را بنامید و در ابتدا
102
00:03:38,159 –> 00:03:40,400
یک بار از صفر شروع می شود. ما در اینجا تصمیم خود را می
103
00:03:40,400 –> 00:03:42,159
گیریم سپس آن را به سمت راست تغییر می دهیم
104
00:03:42,159 –> 00:03:43,599
و سپس تصمیم خود را در
105
00:03:43,599 –> 00:03:45,360
اینجا می گیریم و سپس این کار را برای
106
00:03:45,360 –> 00:03:47,519
هر مقدار در ورودی ادامه می دهیم، اما
107
00:03:47,519 –> 00:03:48,959
بیایید با اولین تصمیم خود شروع کنیم که همان تصمیم است.
108
00:03:48,959 –> 00:03:51,040
ما آن
109
00:03:51,040 –> 00:03:54,000
یکی را اضافه میکنیم، سپس آرایهای از
110
00:03:54,000 –> 00:03:56,400
یکی خواهیم داشت که این زیرمجموعه تا اینجای کار ما بوده است، اگر فهرستی
111
00:03:56,400 –> 00:03:58,000
را وارد نکنیم که
112
00:03:58,000 –> 00:04:00,319
میخواهیم یک لیست خالی داشته باشیم که هنوز یک
113
00:04:00,319 –> 00:04:02,640
زیرمجموعه معتبر است اما کارمان تمام نشده است. با این حال ما
114
00:04:02,640 –> 00:04:04,000
هنوز باید در بقیه آرایه تکرار کنیم
115
00:04:04,000 –> 00:04:05,760
، بنابراین در مرحله بعد در تصمیم دوم هستیم
116
00:04:05,760 –> 00:04:08,239
که دو مقدار است، بنابراین برای اینجا
117
00:04:08,239 –> 00:04:10,480
می توانیم این دو را اضافه کنیم و اگر
118
00:04:10,480 –> 00:04:12,319
این دو را اضافه کنیم، یک دو خواهیم داشت یا
119
00:04:12,319 –> 00:04:14,319
نمی توانیم این دو را اضافه کنیم تا اساساً از این
120
00:04:14,319 –> 00:04:16,320
دو بگذریم که باعث
121
00:04:16,320 –> 00:04:18,959
میشود در اینجا یک مورد مشابه داشته باشیم، میتوانیم
122
00:04:18,959 –> 00:04:21,918
دو مورد را اضافه کنیم که به خودی خود دو
123
00:04:21,918 –> 00:04:23,199
در یک آرایه است
124
00:04:23,199 –> 00:04:24,639
یا میتوانیم از این دو بگذریم
125
00:04:24,639 –> 00:04:27,440
که این یک لیست خالی باقی میماند. هنوز
126
00:04:27,440 –> 00:04:29,440
خوب است، بنابراین ما این مقدار را به پایان رساندیم، اکنون
127
00:04:29,440 –> 00:04:31,280
در دو دوم هستیم و ادامه می
128
00:04:31,280 –> 00:04:34,080
دهیم این نوع رویکرد ساده لوحانه است، اما
129
00:04:34,080 –> 00:04:36,080
اکنون خواهید دید که مشکل چیست،
130
00:04:36,080 –> 00:04:39,040
بنابراین در اینجا فرض کنید این را به آن اضافه
131
00:04:39,040 –> 00:04:41,759
کنیم که اگر
132
00:04:41,759 –> 00:04:45,520
این دو را اضافه نکنیم، به عنوان یک دو باقی میمانیم
133
00:04:45,520 –> 00:04:47,040
و در اینجا میمانیم. میبینید
134
00:04:47,040 –> 00:04:49,120
مشکل کجاست، بنابراین در اینجا میتوانیم یک دو را اضافه کنیم
135
00:04:49,120 –> 00:04:51,919
که به ما یک دو میدهد. میبینید
136
00:04:51,919 –> 00:04:54,720
که ما دو زیر مجموعه داریم که
137
00:04:54,720 –> 00:04:56,479
الان دقیقاً یکسان هستند، حتی اگر
138
00:04:56,479 –> 00:04:58,960
هنوز با آرایه تمام نشدهایم.
139
00:04:58,960 –> 00:05:01,199
این مسیرها به وضوح به
140
00:05:01,199 –> 00:05:03,039
زیرمجموعه های مشابهی منتهی می شوند زیرا آنها
141
00:05:03,039 –> 00:05:05,759
دقیقاً یکسان هستند و بقیه
142
00:05:05,759 –> 00:05:07,360
آرایه برای هر دوی آنها یکسان خواهد بود
143
00:05:07,360 –> 00:05:08,960
بنابراین ما به
144
00:05:08,960 –> 00:05:11,120
زیر مجموعه های تکراری خواهیم رسید اما
145
00:05:11,120 –> 00:05:13,199
سؤال مهم این است که چگونه این اتفاق افتاد و چگونه
146
00:05:13,199 –> 00:05:15,360
می توانیم از این اتفاق جلوگیری کنیم، بیایید
147
00:05:15,360 –> 00:05:18,080
نگاهی بیندازیم تا زمانی که این درخت تصمیم را می گیریم،
148
00:05:18,080 –> 00:05:19,840
به عنوان مثال وقتی اینجا
149
00:05:19,840 –> 00:05:22,400
هستیم و در مقدار 2 هستیم، می دانیم که
150
00:05:22,400 –> 00:05:24,880
همه زیر مجموعه هایی که این یکی را دنبال می کنند مانند
151
00:05:24,880 –> 00:05:27,520
درخت تصمیم را پایین می آوریم که همه زیرمجموعه
152
00:05:27,520 –> 00:05:30,160
ها حداقل یکی را شامل می شوند
153
00:05:30,160 –> 00:05:32,000
ارزش e درست است و تصمیمی که
154
00:05:32,000 –> 00:05:34,720
155
00:05:34,720 –> 00:05:36,800
میگیریم اشکالی ندارد، ما این دو را در نظر میگیریم، بنابراین اگر این دو را وارد کنیم،
156
00:05:36,800 –> 00:05:39,199
میگوییم همه زیرمجموعههایی که با استفاده از
157
00:05:39,199 –> 00:05:41,919
این یکی ایجاد میکنیم حداقل یک مقدار دو را شامل میشوند،
158
00:05:41,919 –> 00:05:44,960
بنابراین این مسیر
159
00:05:44,960 –> 00:05:47,600
قرار است مسیری با تمام زیرمجموعههایی باشد که
160
00:05:47,600 –> 00:05:50,160
شامل حداقل یک دو باشد و ما
161
00:05:50,160 –> 00:05:52,320
تکراری نمیخواهیم، بنابراین وقتی تص
162
00:05:52,320 –> 00:05:55,039
یم میگیریم در سمت راست جایی که از ای
163
00:05:55,039 –> 00:05:57,280
دو مقدار رد میشویم، دو مق
164
00:05:57,280 –> 00:06:00,000
ار را در سمت راست درج نمیکنیم. بنابراین آنچه این
165
00:06:00,000 –> 00:06:02,720
سمت راست باید نشان دهد همه
166
00:06:02,720 –> 00:06:05,919
زیرمجموعه های ممکن است که شامل
167
00:06:05,919 –> 00:06:08,720
حداقل یک دو واحد نمی شود، اساساً همه زیر مجموعه
168
00:06:08,720 –> 00:06:12,400
ها که شامل هیچ دو مقدار نمی شوند،
169
00:06:12,400 –> 00:06:16,000
چرا که این سمت چپ در اینجا قبلاً
170
00:06:16,000 –> 00:06:18,880
شامل همه زیر مجموعه هایی است که حداقل
171
00:06:18,880 –> 00:06:22,080
یک مقدار دو مقدار دارند. اگر هر دو
172
00:06:22,080 –> 00:06:23,759
مقدار را در سمت راست قرار دهیم، در
173
00:06:23,759 –> 00:06:25,440
نهایت با موارد تکراری مواجه میشویم، بنابراین کاری که باید
174
00:06:25,440 –> 00:06:28,720
انجام دهیم این است که هیچ دو مقدار را
175
00:06:28,720 –> 00:06:31,600
در سمت راست قرار ندهیم، چگونه میتوانیم این کار را به خوبی انجام دهیم،
176
00:06:31,600 –> 00:06:34,639
زمانی که اینجا بودیم.
177
00:06:34,639 –> 00:06:36,479
ما در چه زمانی درست تصمیم می گرفتیم
178
00:06:36,479 –> 00:06:38,800
ما انتخاب می کنیم که از این دو بگذریم، باید
179
00:06:38,800 –> 00:06:41,440
هر دو را رد کنیم، بنابراین به جای
180
00:06:41,440 –> 00:06:43,120
اینکه نشانگر i خود را برداریم و فقط
181
00:06:43,120 –> 00:06:45,520
آن را با یک جابجا کنیم تا اینجا باشیم،
182
00:06:45,520 –> 00:06:48,319
در واقع باید آن را با دو تغییر دهیم تا اینجا باشیم،
183
00:06:48,319 –> 00:06:50,160
زیرا اینطوری می دانیم که نیستیم
184
00:06:50,160 –> 00:06:53,280
دو مقدار دیگر دریافت خواهیم کرد، اما
185
00:06:53,280 –> 00:06:55,759
این نمایش ورودی ممکن است آن
186
00:06:55,759 –> 00:06:58,000
را ساده به نظر برساند، اما ما در واقع
187
00:06:58,000 –> 00:07:00,240
تضمینی نداریم که آرایه
188
00:07:00,240 –> 00:07:02,240
ورودی مرتب شود، بنابراین باید خودمان آن را مرتب
189
00:07:02,240 –> 00:07:05,120
کنیم که n log n
190
00:07:05,120 –> 00:07:06,800
زمان است، اما این مشکل بزرگی نیست زیرا
191
00:07:06,800 –> 00:07:08,400
ما از قبل می دانیم که پیچیدگی زمانی
192
00:07:08,400 –> 00:07:10,319
راه حل حدود n
193
00:07:10,319 –> 00:07:12,160
برابر 2 به توان n خواهد بود، بنابراین این
194
00:07:12,160 –> 00:07:14,400
بسیار ناچیز است، بنابراین اکنون اجازه دهید
195
00:07:14,400 –> 00:07:17,120
این درخت تصمیم را دوباره ترسیم کنیم و آنچه را که
196
00:07:17,120 –> 00:07:19,039
قبلاً در ذهن ذکر کردم، ترسیم کنیم. سپس
197
00:07:19,039 –> 00:07:21,520
همه موارد تکراری را حذف می کنیم،
198
00:07:21,520 –> 00:07:23,520
بنابراین این می تواند در واقع یکسان بماند،
199
00:07:23,520 –> 00:07:24,880
زیرا این سمتی است که
200
00:07:24,880 –> 00:07:26,800
ما یک دو را اضافه می کنیم، اما این سمتی است که در آن
201
00:07:26,800 –> 00:07:29,039
از همه دو مقدار صرف نظر می کنیم تا
202
00:07:29,039 –> 00:07:30,960
هنگام تصمیم گیری نشانگر ما باشد. در حال
203
00:07:30,960 –> 00:07:32,720
حاضر در واقع رفتن نیست در اینجا بودن
204
00:07:32,720 –> 00:07:34,319
نشانگر ما در واقع در
205
00:07:34,319 –> 00:07:36,319
اینجا در این 3 خواهد بود. بنابراین آیا
206
00:07:36,319 –> 00:07:39,199
ما یک 3 را وارد می کنیم یا نه این انتخاب ماست، بنابراین
207
00:07:39,199 –> 00:07:41,919
اگر 3 را وارد کنیم، اگر 3 را وارد نکنیم، 1 3 دریافت می کنیم.
208
00:07:41,919 –> 00:07:45,440
ما فقط یکی را خوب می گیریم
209
00:07:45,440 –> 00:07:47,440
و در مورد این دو خوب، ما یکی دو را انتخاب کردیم،
210
00:07:47,440 –> 00:07:49,120
بنابراین اکنون تصمیم بعدی این است
211
00:07:49,120 –> 00:07:50,800
که آیا دو مورد دوم را
212
00:07:50,800 –> 00:07:53,039
در نظر بگیریم یا دو مورد دوم را لحاظ نمی
213
00:07:53,039 –> 00:07:55,520
کنیم تا بتوانیم آن را ترسیم کنیم، بنابراین اگر
214
00:07:55,520 –> 00:07:58,800
دو مورد دوم را وارد کنیم. ما یک دو 2 دریافت می کنیم و
215
00:07:58,800 –> 00:08:01,120
اگر دو مورد دوم را در
216
00:08:01,120 –> 00:08:04,000
نظر نگیریم، فقط به عنوان دو نفر مجرد می مانیم و در نهایت در
217
00:08:04,000 –> 00:08:05,759
سمت راست اینجا قرار داریم، در واقع
218
00:08:05,759 –> 00:08:08,879
از بین دو دومی انتخاب
219
00:08:08,879 –> 00:08:10,639
می کنیم خیر، زیرا ما قبلاً از دو مورد اول صرف نظر کرده ا