Search problems involving combinations and permutations can often be solved using a unified recursive backtracking template.

Template Structure

• Define the output container.
• Handle input edge cases.
• Invoke a recursive helper that builds results starting from a given partial solution.
• Recursive helper follows three principles:
  1. Definition: Accept curent state parameters, produce no direct return value, but populate the result set with completed solutions derived from the current partial state.
  2. Decomposition: Iterate over remaining candidates, append one candidate to the partial solution, recurce, then remove it (backtrack).
  3. Terminasion: Occurs naturally when no further candidates can extend the partial solution.

Time complexity for combination generation: O(k * 2^n) where k is the average subset size and n is the number of input elements.

Generating All Subsets

Given a collection of distinct integers, produce every possible subset. For example, input [1,2,3] yields:

[
  [],
  [1],
  [2],
  [3],
  [1,2],
  [1,3],
  [2,3],
  [1,2,3]
]

Implementation

import java.util.*;

public class SubsetBuilder {
    public List<List<Integer>> generateSubsets(int[] source) {
        List<List<Integer>> output = new ArrayList<>();
        if (source == null || source.length == 0) return output;
        
        Arrays.sort(source);
        buildSubsets(source, 0, new ArrayList<>(), output);
        return output;
    }

    private void buildSubsets(int[] arr, int pos, List<Integer> current, List<List<Integer>> res) {
        res.add(new ArrayList<>(current));
        for (int idx = pos; idx < arr.length; idx++) {
            current.add(arr[idx]);
            buildSubsets(arr, idx + 1, current, res);
            current.remove(current.size() - 1);
        }
    }
}

The recursion starts with an empty list, progressively including elements at and after the current position, ensuring each subset appears exactly once.

Generating All Permutations

Given a list of unique numbers, enumerate all possible orderings. Example: [1,2,3] produces six arrangements:

[
  [1,2,3], [1,3,2],
  [2,1,3], [2,3,1],
  [3,1,2], [3,2,1]
]

Implementation

import java.util.*;

public class PermutationGenerator {
    public List<List<Integer>> getAllPermutations(int[] data) {
        List<List<Integer>> result = new ArrayList<>();
        if (data == null) return result;
        if (data.length == 0) {
            result.add(new ArrayList<>());
            return result;
        }
        collectPermutations(data, new ArrayList<>(), result);
        return result;
    }

    private void collectPermutations(int[] pool, List<Integer> temp, List<List<Integer>> accumulator) {
        if (temp.size() == pool.length) {
            accumulator.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < pool.length; i++) {
            if (temp.contains(pool[i])) continue;
            temp.add(pool[i]);
            collectPermutations(pool, temp, accumulator);
            temp.remove(temp.size() - 1);
        }
    }
}

Here, the algorithm starts from an empty sequence, picks unused numbers iteratively, and backtracks when a full-length permutation is formed.

Search Strategy Comparison

• Depth-First Search (DFS): Begins with an empty set, extends by adding one element at a time until no more additions are possible, then retracts the last addition and explores alternative branches.
• Breadth-First Search (BFS): Explores all subsets of size k before proceeding to size k+1, typically implemented with a queue rather than recursion.