Backtracking

Recently I have been solving some backtracking problems. They look easy, but they are not actually easy. Implementation skill matters, but the more important skill is the ability to solve the problem itself.

I still need a lot of practice. If I solve around 20 similar problems, I think I will start to feel more confident.

78. Subsets

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1

Input:
    [1,2,3]
Output:
[
    [],
    [1],
    [2],[1,2],
    [3],[1,3],[2,3],[1,2,3]
]

I can see a pattern here.

[
    0:[],
    1:[1], // add 1 to each element from the previous result
    2:[2],[1,2], // add 2 to each element from the previous result
    3:[3],[1,3],[2,3],[1,2,3] // add 3 to each element from the previous result
]

[] = []
[][1] = copy [] from the previous line, then insert 1 into []
[][1] [2][1,2] = copy [][1] from the previous line, then insert 2 into [][1] to make [2][1,2]
[][1][2][1,2] [3][1,3][2,3][1,2,3] = copy [][1][2][1,2] from the previous line, then insert 3 into [][1][2][1,2] to make [3][1,3][2,3][1,2,3]

It took some time, but I was still able to think through and solve this one on my own.

Solution

pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut ret = vec![vec![]];
    for n in nums.iter(){
        for r in 0..ret.len(){
            let mut x = ret[r].clone();
            x.push(*n);
            ret.push(x);
        }
    }
    ret
}

39. Combination Sum

Problem

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

The given numbers can be used repeatedly, and the order of arrangement does not matter. In other words, [2,3,5] and [2,5,3] are treated as the same combination.

If the input is [2,3,6,7], the first approach to try is DFS, plugging in each number one by one.

[2]
[2,2]
[2,2,2]
[2,2,2,2]
[2,2,2,3]
[2,2,2,6]
[2,2,2,7]
[2,2,3] 2+2+3 is 7, we don't need go down to [2,2,3,2]
[2,2,6]
[2,2,7]
[2,3]
.
.
.

If I list them one by one, it forms a tree where each node has four children.

                                2
        22      |       23        |      26         |       27
222 223 226 227 | 232 233 236 237 | 262 263 266 267 | 272 273 276 277
.
.
.
                                3
        32      |       33        |      36         |       37
322 333 326 327 | 323 333 336 337 | 326 336 366 267 | 327 337 367 377
.
.
.

But if we do it this way, duplicates such as [2,2,3], [2,3,2], and [3,2,2] appear.

I got stuck here and struggled for almost an hour. After trying several things and then checking the solution, I found that the fix was surprisingly simple: increase the starting point by one each time the loop or recursion advances.

For example, start from 0..input.len, then 1..input.len, then 2..input.len. The execution order becomes something like this.

                                2
        22      |       23        |      26         |       27
222 223 226 227 |     233 236 237 |         266 267 |            277
.
.
.
                                3
                |       33        |      36         |       37
                |     333 336 337 |         366 267 |            377
.
.
.

Once you understand the ordering, the idea is simple. When starting from 2, all combinations that include 2 have already been listed. So when the next loop starts, it must not create combinations that include 2 again. At that point, all combinations containing 2 are done, so only combinations without 2 need to be listed. That is why the next start is 3. Similarly, once all combinations containing 3 are complete, we exclude 3 and list combinations starting from 6.

Solution

pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>>{
    let mut output: Vec<Vec<i32>> = vec![];
    let mut path = vec![];
    Solution::dfs(0,&mut path, &candidates, target,&mut output);
    output
}
pub fn dfs(i:usize, path:&mut Vec<i32>, can:&[i32], target: i32, output: &mut Vec<Vec<i32>>){
    let sum = path.iter().fold(0,|p,n|p+n);
    if sum == target{
        output.push(path.clone());
        return;
    }
    if sum>target || i >= can.len(){
        return;
    }
    for j in i..can.len(){
        path.push(can[j]);
        Solution::dfs(j,&mut path.clone(),can,target,output);
        path.pop();
    }
}

40. Combination Sum II

Problem

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
]

Example 2

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
    [1,2,2],
    [5]
]

This is the same as Combination Sum I except that each number cannot be reused. In the example, [1,1,6] is possible not because we reused the same number, but because the given numbers contain two 1s.

If we visit every node with DFS, we run into the same duplicate problem as before.

Can we solve it like Combination Sum I by excluding one number every time the loop advances? That worked in Combination Sum I because every number in the array was unique. Here, duplicate values exist, so we need one more step.

Take [10,1,2,7,6,1,5] as an example. Suppose we create every combination containing 10, then try to create combinations containing 1. Since 1 appears twice in [10,1,2,7,6,1,5], combinations containing 1 will eventually appear again.

To avoid duplicates, sort first, turning [10,1,2,7,6,1,5] into [1,1,2,5,6,7,10], and skip to the next number when a combination has already been created.

                                1
        11      |       12        |      15         |       16
112 115 116 117 |      125 126 127|         156 157 |               167
.
.
.

Look at this. It shows part of the combinations that can be created from the first 1. If we start combinations from the second 1, combinations containing two 1s such as 112, 115, 116, and 117 will not appear, but combinations containing only one 1, such as 12, 15, 16, 125, 126, 127, 156, and 157, can appear again. That is why numbers that have already appeared must be skipped.

Solution

pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut path = vec![];
    let mut output = vec![];
    candidates.sort();
    Self::dfs(0, path, &candidates, target, &mut output);
    output
}
pub fn dfs(i:usize, mut path: Vec<i32>, can:&[i32],target:i32, output:&mut Vec<Vec<i32>>){
    if target ==0 {
        output.push(path.clone());
        return;
    } else if target < 0{
        return;
    }

    for j in i..can.len(){
        if j > i && can[j] == can[j - 1] {
            continue;
        }
        path.push(can[j]);
        Self::dfs(j+1,path.clone(),can,target-can[j],output);
        path.pop();
    }
}

What changed from Combination Sum I:

1. Sort the array.
2. Skip numbers already checked in the array.
3. When calling recursively, pass index + 1 to avoid reusing the same element.