Freaks City

Suppose you are given an integer array arr. The goal is to split it into the fewest possible subsets such that every pair of elements inside the same subset is coprime (their greatest common divisor equals 1). We can solve this problem using a DFS backtracking approach. Below are two distinct strategies, each corresponding to a different way of ...

Recursion can be categorized into path-aware and path-unaware forms. Most tree-related recursions are path-aware. Fundamentally, recursion implements depth-first search (DFS). To solve problems recursively, treat the recursive function as a black box that handles a subproblem, then reuse it. Beginners often try to fully expand the recursion, wh ...

The word chain problem involves constructing the longest possilbe sequence ("dragon") from a given set of words, starting with a specified character. Each word may be used at most twice in the chain. When two words are joined, overlapping parts are merged into one—e.g., beast and astonish form beastonish. Importantly, no word in the c ...

Problem 216: Combination Sum III Description: Given two integers k and n, find all possible combinations of k numbers from 1 to 9 that add up to n. Each number can only be used once in a combination. Approach This problem requires finding subsets of size k from the set [1,2,3,4,5,6,7,8,9] where the sum equals n. The parameter k represents the d ...

Generating the complete power set of a collection involves binary decisions at each element. The recursive approach branches twice: once including the current element and once excluding it. public void enumerateSubsets(int[] data, List<Integer> buffer, int idx) { if (idx == data.length) { System.out.println(buffer); re ...

153. Minimum in Rotated Sorted Array Approach A rotated sorted array is formed by shifting elements from the end to the beginning. For instance, rotating [0,1,2,4,5,6,7] four times yields [4,5,6,7,0,1,2]. To find the minimum element efficiently, use binary search. Compare the middle element with the rightmost element: If arr[mid] < arr[righ ...

Permutations This article demonstrates a method for generating all permutations of a set of numbers using depth-first search (DFS). #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_SIZE = 100010; int size, sequence[MAX_SIZE]; bool visited[MAX_SIZE]; void generatePermutations(int ...

Overview of Backtracking Backtracking is a systematic way to explore all potential solutions by building combinations incrementally and backtracking when a path fails to meet constraints. It's particularly useful for problems like combinations, permutations, subsets, and other combinatorial searches. Common problem types solved with backtrackin ...

1. Gymnastic Team Formation Given the small input constraints, a brute-force approach with backtracking and pruning is suitable. The solution uses depth-first search (DFS) to explore valid permutations while eliminating invalid paths early. #include <iostream> using namespace std; int constraints[11] = {0}; bool used[11] = {false}; int v ...

Recursive Permutation Generation This approach generates all permutations through recursive swaps. The algorithm fixes each character at the first position and recursively permutes the remaining substring. public class PermutationGenerator { public static void main(String[] args) { String text = "abc"; permute( ...