Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Move from brute-force thinking to an efficient approach using backtracking strategy.
Design the CombinationIterator class:
CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.next() Returns the next combination of length combinationLength in lexicographical order.hasNext() Returns true if and only if there exists a next combination.Example 1:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]
Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
Constraints:
1 <= combinationLength <= characters.length <= 15characters are unique.104 calls will be made to next and hasNext.next are valid.Problem summary: Design the CombinationIterator class: CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments. next() Returns the next combination of length combinationLength in lexicographical order. hasNext() Returns true if and only if there exists a next combination.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking · Design
["CombinationIterator","next","hasNext","next","hasNext","next","hasNext"] [["abc",2],[],[],[],[],[],[]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1286: Iterator for Combination
class CombinationIterator {
private int n;
private int combinationLength;
private String characters;
private StringBuilder t = new StringBuilder();
private List<String> cs = new ArrayList<>();
private int idx = 0;
public CombinationIterator(String characters, int combinationLength) {
n = characters.length();
this.combinationLength = combinationLength;
this.characters = characters;
dfs(0);
}
public String next() {
return cs.get(idx++);
}
public boolean hasNext() {
return idx < cs.size();
}
private void dfs(int i) {
if (t.length() == combinationLength) {
cs.add(t.toString());
return;
}
if (i == n) {
return;
}
t.append(characters.charAt(i));
dfs(i + 1);
t.deleteCharAt(t.length() - 1);
dfs(i + 1);
}
}
/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator obj = new CombinationIterator(characters, combinationLength);
* String param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
// Accepted solution for LeetCode #1286: Iterator for Combination
type CombinationIterator struct {
cs []string
idx int
}
func Constructor(characters string, combinationLength int) CombinationIterator {
t := []byte{}
n := len(characters)
cs := []string{}
var dfs func(int)
dfs = func(i int) {
if len(t) == combinationLength {
cs = append(cs, string(t))
return
}
if i == n {
return
}
t = append(t, characters[i])
dfs(i + 1)
t = t[:len(t)-1]
dfs(i + 1)
}
dfs(0)
return CombinationIterator{cs, 0}
}
func (this *CombinationIterator) Next() string {
ans := this.cs[this.idx]
this.idx++
return ans
}
func (this *CombinationIterator) HasNext() bool {
return this.idx < len(this.cs)
}
/**
* Your CombinationIterator object will be instantiated and called as such:
* obj := Constructor(characters, combinationLength);
* param_1 := obj.Next();
* param_2 := obj.HasNext();
*/
# Accepted solution for LeetCode #1286: Iterator for Combination
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
def dfs(i):
if len(t) == combinationLength:
cs.append(''.join(t))
return
if i == n:
return
t.append(characters[i])
dfs(i + 1)
t.pop()
dfs(i + 1)
cs = []
n = len(characters)
t = []
dfs(0)
self.cs = cs
self.idx = 0
def next(self) -> str:
ans = self.cs[self.idx]
self.idx += 1
return ans
def hasNext(self) -> bool:
return self.idx < len(self.cs)
# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()
// Accepted solution for LeetCode #1286: Iterator for Combination
#[derive(Default)]
struct CombinationIterator {
combinations: Vec<String>,
index: usize,
}
impl CombinationIterator {
fn new(characters: String, combination_length: i32) -> Self {
let n = combination_length as usize;
let m = characters.len();
let mut indexes = vec![];
let mut combinations = vec![];
let s: Vec<char> = characters.chars().collect();
Self::dfs(0, &mut indexes, &mut combinations, &s, n, m);
let index = 0;
CombinationIterator {
combinations,
index,
}
}
fn dfs(
start: usize,
indexes: &mut Vec<usize>,
combinations: &mut Vec<String>,
s: &[char],
n: usize,
m: usize,
) {
if indexes.len() == n {
let t: String = indexes.iter().map(|&i| s[i]).collect();
combinations.push(t);
} else {
for i in start..m {
indexes.push(i);
Self::dfs(i + 1, indexes, combinations, s, n, m);
indexes.pop();
}
}
}
fn next(&mut self) -> String {
let res = self.combinations[self.index].to_string();
self.index += 1;
res
}
fn has_next(&self) -> bool {
self.index < self.combinations.len()
}
}
#[test]
fn test() {
let mut iter = CombinationIterator::new("abc".to_string(), 2);
assert_eq!(iter.has_next(), true);
assert_eq!(iter.next(), "ab".to_string());
assert_eq!(iter.has_next(), true);
assert_eq!(iter.next(), "ac".to_string());
assert_eq!(iter.has_next(), true);
assert_eq!(iter.next(), "bc".to_string());
assert_eq!(iter.has_next(), false);
}
// Accepted solution for LeetCode #1286: Iterator for Combination
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1286: Iterator for Combination
// class CombinationIterator {
// private int n;
// private int combinationLength;
// private String characters;
// private StringBuilder t = new StringBuilder();
// private List<String> cs = new ArrayList<>();
// private int idx = 0;
//
// public CombinationIterator(String characters, int combinationLength) {
// n = characters.length();
// this.combinationLength = combinationLength;
// this.characters = characters;
// dfs(0);
// }
//
// public String next() {
// return cs.get(idx++);
// }
//
// public boolean hasNext() {
// return idx < cs.size();
// }
//
// private void dfs(int i) {
// if (t.length() == combinationLength) {
// cs.add(t.toString());
// return;
// }
// if (i == n) {
// return;
// }
// t.append(characters.charAt(i));
// dfs(i + 1);
// t.deleteCharAt(t.length() - 1);
// dfs(i + 1);
// }
// }
//
// /**
// * Your CombinationIterator object will be instantiated and called as such:
// * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
// * String param_1 = obj.next();
// * boolean param_2 = obj.hasNext();
// */
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.