algorithm - construct Backtrack function from state-space tree - Stack Overflow

admin管理员组

文章数量:1356709

Q. How do I decide whether to pass i+1 or j+1 in the recursive call when constructing a backtracking function from a state-space tree diagram?

Key Insights I develop from the state-space tree diagram:

1. Include/Exclude Pattern (O(2^n))

• Used when each element has two choices (include or exclude).
• No need for a loop.

The recursive call usually advances the index (i+1) to move to the next element.

void backtrack(int i, vector<int>& subset) {
    if (i == n) {
        // Process subset
        return;
    }

    // Include element i
    subset.push_back(arr[i]);
    backtrack(i + 1, subset);
    subset.pop_back(); // Undo change

    // Exclude element i
    backtrack(i + 1, subset);
}

Example: Subsets Problem

2. Loop-Based Pattern (O(n!))

• Used when there are multiple choices for each level.
• A for loop is needed to explore all possibilities.

If elements can be used multiple times, j is passed unchanged. If each element is used only once, pass j+1 to avoid reusing elements.

void backtrack(int i, vector<int>& combination) {
    if (combination.size() == target_size) {
        // Process valid combination
        return;
    }

    for (int j= i; j < n; j++) {
        if (isValid(arr[j])) {  // Pruning condition
            combination.push_back(arr[j]);
            backtrack(j + 1, combination);  // Pass j+1 for unique choices
            combination.pop_back();  // Undo changes
        }
    }
}

Example: Combinations Problem

3. we only need undo operation only if the partialsolution is pass by ref.

Q. How do I decide whether to pass i+1 or j+1 in the recursive call when constructing a backtracking function from a state-space tree diagram?

Key Insights I develop from the state-space tree diagram:

1. Include/Exclude Pattern (O(2^n))

• Used when each element has two choices (include or exclude).
• No need for a loop.

The recursive call usually advances the index (i+1) to move to the next element.

void backtrack(int i, vector<int>& subset) {
    if (i == n) {
        // Process subset
        return;
    }

    // Include element i
    subset.push_back(arr[i]);
    backtrack(i + 1, subset);
    subset.pop_back(); // Undo change

    // Exclude element i
    backtrack(i + 1, subset);
}

Example: Subsets Problem

2. Loop-Based Pattern (O(n!))

• Used when there are multiple choices for each level.
• A for loop is needed to explore all possibilities.

If elements can be used multiple times, j is passed unchanged. If each element is used only once, pass j+1 to avoid reusing elements.

void backtrack(int i, vector<int>& combination) {
    if (combination.size() == target_size) {
        // Process valid combination
        return;
    }

    for (int j= i; j < n; j++) {
        if (isValid(arr[j])) {  // Pruning condition
            combination.push_back(arr[j]);
            backtrack(j + 1, combination);  // Pass j+1 for unique choices
            combination.pop_back();  // Undo changes
        }
    }
}

Example: Combinations Problem

3. we only need undo operation only if the partialsolution is pass by ref.

• algorithm
• backtracking

Share Improve this question Follow edited Mar 28 at 5:12 Mr. Ghosh asked Mar 28 at 4:52 Mr. GhoshMr. Ghosh 4377 bronze badges 2

• 1 Your code examples are reasonably clear, but what is your actual question? I think you need to clarify what answer you are looking for. – njlarsson Commented Mar 28 at 7:01
• "from a state-space tree diagram": which one are you asking about? Please focus your question on a specific task. – trincot Commented Mar 28 at 7:40

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

I think your examples help answer your question. As a general rule of thumb:

• if the tree is binary, your recursive call usually advances to the index (i+1).

• If elements can be used multiple times, j is passed unchanged. to allow for repetition and reusing of elements.

• If each element is used only once, and your tree is not binary, pass (j+1) to avoid reusing elements.

本文标签： algorithmconstruct Backtrack function from statespace treeStack Overflow