Subsets
FUNCTION findSubsets(arr):
subsets = [[]] # Initialize with an empty subset
FOR each num IN arr:
newSubsets = []
# Generate new subsets by adding the current element
FOR each subset IN subsets:
newSubsets.append(subset + [num])
subsets.extend(newSubsets) # Add new subsets to the result
RETURN subsetsSubsets
Let’s solve the Subsets problem using the Subsets pattern.
Statement
Given an array of integers, nums, find all possible subsets of nums, including the empty set.
Note: The solution set must not contain duplicate subsets. You can return the solution in any order.
Constraints:
1≤1≤ nums.length ≤10≤10 −10≤−10≤ nums[i] ≤10≤10 All the numbers of nums are unique.
import java.util.*;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
// Base case: add current subset
result.add(new ArrayList<>(path));
// Try including/skipping remaining elements
for (int i = index; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() - 1); // Backtrack
}
}
}
With possible duplicates in nums
import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // CRITICAL: groups duplicates
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start, List<Integer> path,
List<List<Integer>> result) {
result.add(new ArrayList<>(path)); // Every path is valid subset
for (int i = start; i < nums.length; i++) {
// KEY: Skip duplicates at same level (works because sorted)
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() - 1); // Backtrack
}
}
}
~~~
class FindSubsets {
static int getBit(int num, int bit) {
int temp = (1 «_space;bit);
temp = temp & num;
if (temp == 0) {
return 0;
}
return 1;
}
static List<List<Integer>> findAllSubsets(int[] nums) {
List<List<Integer>> setsList = new ArrayList<>();
if (nums.length != 0) {
int subsetsCount = (int) (Math.pow(2, nums.length));
for (int i = 0; i < subsetsCount; ++i) {
List<Integer> subset = new ArrayList<>();
for (int j = 0; j < nums.length; ++j) {
if (getBit(i, j) == 1) {
int x = nums[j];
subset.add(x);
}
}
setsList.add(subset);
}
} else {
List<Integer> emptySet = new ArrayList<>();
setsList.add(emptySet);
}
return setsList;
}Permutations
Let’s solve the Permutations problem using the Subsets pattern.
Statement
Given an input string, word, return all possible permutations of the string.
Note: The order of permutations does not matter.
Constraints:
All characters in word are unique. 1≤1≤ word.length ≤6≤6 All characters in word are lowercase English letters.
public static String swapChar(String word,int i, int j)
{
char[] swapIndex = word.toCharArray();
char temp = swapIndex[i];
swapIndex[i] = swapIndex[j];
swapIndex[j] = temp;
return new String(swapIndex);
}
public static void permuteStringRec(String word, int currentIndex, ArrayList<String> results)
{
if(currentIndex == word.length() - 1)
{
results.add(word);
return ;
}
for (int index = currentIndex; index < word.length(); index++)
{
String swappedStr = swapChar(word, currentIndex, index);
permuteStringRec(swappedStr, currentIndex + 1, results);
}
}
public static ArrayList<String> permuteWord(String word)
{
ArrayList<String> results = new ArrayList<String>();
permuteStringRec(word, 0, results);
return results;
}Letter Combinations of a Phone Number
Let’s solve the Letter Combinations of a Phone Number problem using the Subsets pattern.
Statement
Given a string containing digits from 2 to 9 inclusive, with the possibility of each digit appearing multiple times, return all possible letter combinations that the number could represent. Return the answer in any order.
The illustration below shows the mapping of digits to letters in a telephone dial pad.
Note: The number 11 on the telephone dial pad does not correspond to any letter, so the input string only contains digits from 22 to 99.
class LetterCombinations {
// Use backtrack function to generate all possible combinations
public void backtrack(int index, StringBuilder path, String digits, Map<Character, String[]> letters, List<String> combinations) {
if (path.length() == digits.length()) {
combinations.add(path.toString());
return;
}
char digit = digits.charAt(index);
String[] possibleLetters = letters.get(digit);
for (String letter : possibleLetters) {
path.append(letter);
backtrack(index + 1, path, digits, letters, combinations);
path.deleteCharAt(path.length() - 1);
}
}
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String[]> digitsMapping = new HashMap<>();
digitsMapping.put('1', new String[]{""});
digitsMapping.put('2', new String[]{"a", "b", "c"});
digitsMapping.put('3', new String[]{"d", "e", "f"});
digitsMapping.put('4', new String[]{"g", "h", "i"});
digitsMapping.put('5', new String[]{"j", "k", "l"});
digitsMapping.put('6', new String[]{"m", "n", "o"});
digitsMapping.put('7', new String[]{"p", "q", "r", "s"});
digitsMapping.put('8', new String[]{"t", "u", "v"});
digitsMapping.put('9', new String[]{"w", "x", "y", "z"});
backtrack(0, new StringBuilder(), digits, digitsMapping, combinations);
return combinations;
}Generate Parentheses
Let’s solve the Generate Parentheses problem using the Subsets pattern.
Statement
For a given number, n, generate all combinations of balanced parentheses.
Constraints:
1≤1≤ n ≤10≤10
// The recursive backtracking function
static void backtrack(int n, int leftCount, int rightCount, ArrayList<Character> output, ArrayList<String> result) {
// Base case where count of left and right braces is n
if (leftCount >= n && rightCount >= n) {
String outputStr = output.toString();
result.add(outputStr.substring(1, outputStr.length()-1).replace(", ", ""));
}
// Case where we can still add left braces
if (leftCount < n) {
output.add('(');
backtrack(n, leftCount + 1, rightCount, output, result);
output.remove(output.size() - 1);
}
// Case where we add right braces if the current count
// of right braces is less than the count of left braces
if (rightCount < leftCount) {
output.add(')');
backtrack(n, leftCount, rightCount + 1, output, result);
output.remove(output.size() - 1);
}
}Letter Case Permutation
Let’s solve the Letter Case Permutation problem using the Subsets pattern.
Statement
Given a string, s, consisting of letters and digits, generate all possible variations by modifying each letter independently to be either lowercase or uppercase while keeping the digits unchanged. Each letter in the s string can appear in both cases across different variations, resulting in multiple possible combinations. Return a list containing all such variations in any order.
public class Solution
{
// Function to generate all letter case permutations of the given string
public static List<String> letterCasePermutation(String s)
{
List<String> result = new ArrayList<>();
result.add(""); // Initialize result with an empty string
// Iterate over each character in the input string
for (char ch : s.toCharArray())
{
int size = result.size(); // Store current size of result
// Iterate through all existing permutations
for (int i = 0; i < size; i++)
{
String str = result.get(i);
if (Character.isLetter(ch))
{
// If the character is a letter, generate both lowercase and uppercase variations
result.set(i, str + Character.toLowerCase(ch));
result.add(str + Character.toUpperCase(ch));
}
else
{
// If the character is a digit, simply append it to existing permutations
result.set(i, str + ch);
}
}
}
return result;
}**Letter Tile Possibilities
**
Try to solve the Letter Tile Possibilities problem.
Statement
You are given a string, tiles, consisting of uppercase English letters. You can arrange the tiles into sequences of any length (from 1 to the length of tiles), and each sequence must include at most one tile, tiles[i], from tiles.
Your task is to return the number of possible non-empty unique sequences you can make using the letters represented on tiles[i].
import java.util.*;
class Solution {
public int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (char c : tiles.toCharArray()) {
count[c - 'A']++;
}
return dfs(count);
}
private int dfs(int[] count) {
int total = 0;
for (int i = 0; i < 26; i++) {
if (count[i] == 0) continue;
// Each placement forms new sequence(s)
total++;
count[i]--;
// Extend sequence
total += dfs(count);
// Backtrack
count[i]++;
}
return total;
}
}
class Solution {
public int numTilePossibilities(String tiles) {
// 1. Count frequencies (handles alphanumeric + duplicates)
Map<Character, Integer> freq = new HashMap<>();
for (char c : tiles.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
return dfs(freq);
}
// 2. Backtrack: try each unique char with available count
private int dfs(Map<Character, Integer> freq) {
int total = 0;
// 3. Iterate UNIQUE chars only (HashSet skips duplicates)
for (char c : new HashSet<>(freq.keySet())) {
if (freq.get(c) == 0) continue; // Skip exhausted chars
// 4. Use one: creates new sequence + extensions
total++;
freq.put(c, freq.get(c) - 1);
total += dfs(freq); // Recurse for longer sequences
// 5. Backtrack
freq.put(c, freq.get(c) + 1);
}
return total;
}
}
