[LeetCode][39. Combination Sum] Easy Backtracking Approach: Deduplicating and Pruning

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

By Long Luo

This article is the solution Easy Backtracking Approach: Deduplicating and Pruning of Problem 39. Combination Sum.

Backtracking

It’s a typical Backtracking algorithm.

We can easily draw the tree below.

Tree Path

Take \(\textit{target} = 7\) as the root node and subtract the value of the edge while creating a child node.

Stop it when the value of the node is \(0\) or a negative number.

All paths from the root node to leaf node \(0\) are the results of the question.

Let’s coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || target == 0) {
            return ans;
        }

        backtrack(ans, new ArrayList<>(), candidates, target);
        return ans;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int remain) {
        if (remain < 0) {
            return;
        }

        if (remain == 0) {
            res.add(new ArrayList<>(list));
            return;
        }

        int len = candidates.length;
        for (int i = 0; i < len; i++) {
            int num = candidates[i];
            list.add(num);
            backtrack(res, list, candidates, remain - num);
            list.remove(list.size() - 1);
        }
    }
}

Take \(\textit{target} = 7\) for example, \([[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]\) are the answer.

However, the correct answer is \([[7], [2, 2, 3]]\).

Since it requires that each solution is not in order, so the \([2, 2, 3]\) and \([2, 3, 2]\) are the same answer.

What’s problem?

When and how did we duplicate the path?

Why Duplicated?

At each node of the tree, all the candidates were searched and used, so there is a duplicate list.

Is it possible to deduplicate while searching?

Of course we can.

We have to search the elements in order while searching, since the output is not by order. We search from the certain position in the next round.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int start, int remain) {
    if (remain < 0) {
        return;
    }

    if (remain == 0) {
        res.add(new ArrayList<>(list));
        return;
    }

    int len = candidates.length;
    for (int i = start; i < len; i++) {
        int num = candidates[i];
        list.add(num);
        backtrack(res, list, candidates, i, remain - num);
        list.remove(list.size() - 1);
    }
}

By now we deduplicating it and complete the problem.

Pruning

We can prune the tree to make it work more efficiency.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (candidates == null || target == 0) {
            return ans;
        }

        Arrays.sort(candidates);
        backtrack(ans, new ArrayList<>(), candidates, 0, target);
        return ans;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int[] candidates, int begin, int remain) {
        if (remain < 0) {
            return;
        }

        if (remain == 0) {
            res.add(new ArrayList<>(list));
            return;
        }

        int len = candidates.length;
        for (int i = begin; i < len; i++) {
            int num = candidates[i];
            if (remain - num < 0) {
                break;
            }
            list.add(num);
            backtrack(res, list, candidates, i, remain - num);
            list.remove(list.size() - 1);
        }
    }
}

Analysis

  • Time Complexity: \(O(Sum)\), \(Sum\) is all the path.
  • Space Complexity: \(O(\textit{target})\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗