← Back to DSA Course | Chapter 8: Recursion & Backtracking | Lesson 7 of 7

Subset Generation कैसे करें

Subsets generate करना आपके friends में से possible हर team list करने जैसा है, बिल्कुल कोई नहीं से लेकर सब तक।

In this page:

  1. Subset Idea
  2. Include or Exclude
  3. Recursive Generation
  4. Subset Properties
  5. Practice
Syntax
markup 
def subsets(index, current):
    if index == len(nums):
        result.append(current[:])
        return
    subsets(index + 1, current)          # exclude
    current.append(nums[index])
    subsets(index + 1, current)          # include
    current.pop()

Subset Idea

एक set के सभी subsets generate करने का मतलब है इसके elements का हर possible combination produce करना, empty set और पूरा set खुद सहित। यह एक foundational technique है जो तब दिखता है जब कोई problem आपसे items की 'हर possible selection' विचार करने को कहती है।

उदाहरण: Subset Idea

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<int> set = {1, 2};
	cout << "{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set");
	}
}
print("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set")
#include <stdio.h>
int main() {
	printf("{}, {1}, {2}, {1,2} - 4 subsets total for a 2-element set");
	return 0;
}

Include or Exclude

Core recursive idea हर element पर एक binary choice है: इसे बनाए जा रहे current subset में include करें, या इसे skip करें, और दोनों तरह से बाकी elements में recurse करें। Include/skip decisions का हर complete path एक distinct subset produce करता है।

उदाहरण: Include or Exclude

#include <iostream>
#include <vector>
using namespace std;
void subsets(vector<int>& nums, int i, vector<int>& cur) {
	if (i == nums.size()) {
		cout << "{ "; for (int x : cur) cout << x << " "; cout << "}" << endl;
		return;
	}
	subsets(nums, i + 1, cur);
	cur.push_back(nums[i]);
	subsets(nums, i + 1, cur);
	cur.pop_back();
}
int main() {
	vector<int> nums = {1, 2};
	vector<int> cur;
	subsets(nums, 0, cur);
	return 0;
}
import java.util.*;
public class Main {
	static void subsets(int[] nums, int i, List<Integer> cur) {
		if (i == nums.length) { System.out.println(cur); return; }
		subsets(nums, i + 1, cur);
		cur.add(nums[i]);
		subsets(nums, i + 1, cur);
		cur.remove(cur.size() - 1);
	}
	public static void main(String[] args) {
		subsets(new int[]{1, 2}, 0, new ArrayList<>());
	}
}
def subsets(nums, i, cur):
    if i == len(nums):
        print(cur)
        return
    subsets(nums, i + 1, cur)
    cur.append(nums[i])
    subsets(nums, i + 1, cur)
    cur.pop()

subsets([1, 2], 0, [])
#include <stdio.h>
int cur[10], top = 0;
void subsets(int nums[], int i, int n) {
	if (i == n) {
		printf("{ "); for (int j = 0; j < top; j++) printf("%d ", cur[j]); printf("}\n");
		return;
	}
	subsets(nums, i + 1, n);
	cur[top++] = nums[i];
	subsets(nums, i + 1, n);
	top--;
}
int main() {
	int nums[] = {1, 2};
	subsets(nums, 0, 2);
	return 0;
}

Recursive Generation

Recursion naturally इसे प्रति call एक element process करके और चाहे जो भी choice हो अगले element पर move करके model करता है, जब तक हर element decided न हो और एक complete subset record न हो जाए।

उदाहरण: Recursive Generation

#include <iostream>
#include <vector>
using namespace std;
int count = 0;
void subsets(vector<int>& nums, int i, vector<int>& cur) {
	if (i == nums.size()) { count++; return; }
	subsets(nums, i + 1, cur);
	cur.push_back(nums[i]);
	subsets(nums, i + 1, cur);
	cur.pop_back();
}
int main() {
	vector<int> nums = {1, 2, 3};
	vector<int> cur;
	subsets(nums, 0, cur);
	cout << "Total subsets generated: " << count;
	return 0;
}
import java.util.*;
public class Main {
	static int count = 0;
	static void subsets(int[] nums, int i, List<Integer> cur) {
		if (i == nums.length) { count++; return; }
		subsets(nums, i + 1, cur);
		cur.add(nums[i]);
		subsets(nums, i + 1, cur);
		cur.remove(cur.size() - 1);
	}
	public static void main(String[] args) {
		subsets(new int[]{1, 2, 3}, 0, new ArrayList<>());
		System.out.println("Total subsets generated: " + count);
	}
}
count = 0
def subsets(nums, i, cur):
    global count
    if i == len(nums):
        count += 1
        return
    subsets(nums, i + 1, cur)
    cur.append(nums[i])
    subsets(nums, i + 1, cur)
    cur.pop()

subsets([1, 2, 3], 0, [])
print("Total subsets generated:", count)
#include <stdio.h>
int cur[10], top = 0, count = 0;
void subsets(int nums[], int i, int n) {
	if (i == n) { count++; return; }
	subsets(nums, i + 1, n);
	cur[top++] = nums[i];
	subsets(nums, i + 1, n);
	top--;
}
int main() {
	int nums[] = {1, 2, 3};
	subsets(nums, 0, 3);
	printf("Total subsets generated: %d", count);
	return 0;
}

Subset Properties

चूंकि n elements में से हर एक independently include या exclude हो सकता है, बिल्कुल 2^n possible subsets हैं — यह exponential count ही कारण है कि subset generation सिर्फ relatively छोटे input sizes के लिए practical है।

उदाहरण: Subset Properties

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int n = 5;
	cout << n << " elements produce " << (int)pow(2, n) << " subsets";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int n = 5;
		System.out.println(n + " elements produce " + (int) Math.pow(2, n) + " subsets");
	}
}
n = 5
print(n, "elements produce", 2 ** n, "subsets")
#include <stdio.h>
#include <math.h>
int main() {
	int n = 5;
	printf("%d elements produce %d subsets", n, (int)pow(2, n));
	return 0;
}

Practice

यही include-or-exclude recursive pattern 0/1 knapsack और combination-sum जैसी harder problems का direct ancestor है, जो उसी basic subset-generation structure के ऊपर constraints (जैसे एक weight limit या target sum) जोड़ती हैं।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum");
	}
}
print("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum")
#include <stdio.h>
int main() {
	printf("Include-or-exclude recursion is the direct ancestor of 0/1 knapsack and combination-sum");
	return 0;
}
Related Topics

Sudoku Solver कैसे बनाएँ · N-Queens समस्या · Backtracking परिचय · Tower of Hanoi समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. cur को result में बिना copy किए जोड़ना और फिर इसे बदलते रहना।
  2. Include branch के बाद element हटाना भूल जाना (backtracking), इसलिए बाद वाली subsets में extra items होती हैं।
  3. Empty subset missing या 2^n से कम subsets की उम्मीद करना।
चैप्टर सारांश
  • Recursion problems को उनकी खुद की छोटी versions में तोड़कर solve करता है, जैसे Fibonacci, factorial, और Tower of Hanoi में।
  • Backtracking choices try करता है और जब वे fail हों तो उन्हें undo करता है।
  • N-Queens, Sudoku Solver, और subset generation classic backtracking problems हैं।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Sudoku Solver Next Lesson → Bubble Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.