LiSheng's blog
lisheng
2024-09-10
目录

回溯

# 回溯

  • 组合问题：N个数里面按一定规则找出k个数的集合（无序）
  • 排列问题：N个数按一定规则全排列，有几种排列方式（有序）
  • 分割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集（）
  • 棋盘问题：N皇后，解数独等等

# 组合

N个数里面按一定规则找出k个数的集合

# 组合 (opens new window)

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。

func combine(n int, k int) [][]int {
	res := [][]int{}
	path := []int{}
	var dfs func(int)
	dfs = func(i int) {
		if len(path) == k {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return
		}

		for j := i; j <= n; j++ {
			if n-i+1 < k-len(path) {
				break
			}
			path = append(path, j)
			dfs(j + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(1)
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;

        auto dfs = [&](auto&& dfs, int i) {
            if (k == path.size()) {
                res.emplace_back(path);
                return;
            }
            for (int j = i; j <= n; j++) {
                if (n - i + 1 < k - path.size()) {
                    break;
                }
                path.emplace_back(j);
                dfs(dfs, j + 1);
                path.pop_back();
            }
        };

        dfs(dfs, 1);
        return res;
    }
};
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

# 组合总和 (opens new window)（无重复元素、可重复选中）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有_ _不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。


func combinationSum(candidates []int, target int) [][]int {
	res, path := make([][]int, 0), make([]int, 0, len(candidates))
	sort.Ints(candidates)
	var dfs func(start, target int)
	dfs = func(start, target int) {
		if target == 0 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > target {
				break
			}
			path = append(path, candidates[i])
			dfs(i, target-candidates[i])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        // ranges::sort(candidates);
        vector<vector<int>> res;
        vector<int> path;

        auto dfs = [&](auto&& dfs, int i, int left) {
            if (left == 0) {
                res.emplace_back(path);
                return;
            }
            if (i == candidates.size() || left < candidates[i]) {
                return;
            }

            dfs(dfs, i + 1, left);

            path.emplace_back(candidates[i]);
            dfs(dfs, i, left - candidates[i]);
            path.pop_back();
        };

        dfs(dfs, 0, target);
        return res;
    }
};
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

# 组合总和 II (opens new window)（有重复元素、不可重复选中）

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。

在于过滤已经前面已经组合过的相等的数字

func combinationSum2(candidates []int, target int) [][]int {
	res, path := make([][]int, 0), make([]int, 0, len(candidates))
	used := make([]bool, len(candidates))
	sort.Ints(candidates)

	var dfs func(int, int)
	dfs = func(start, target int) {
		if target == 0 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > target {
				break
			}

			if i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false {
				continue
			}

			path = append(path, candidates[i])
			used[i] = true
			dfs(i+1, target-candidates[i])
			used[i] = false
			path = path[:len(path)-1]
		}
	}

	dfs(0, target)
	return res
}
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
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        std::vector<std::vector<int>> res;
        std::vector<int> path;
        std::vector<bool> used(candidates.size(), false);

        // 先对数组进行排序，以便后面能处理重复元素
        std::vector<int> sortedCandidates = candidates;
        std::sort(sortedCandidates.begin(), sortedCandidates.end());

        auto dfs = [&](auto&& dfs, int start, int target) {
            if (target == 0) {
                res.emplace_back(path);
                return;
            }

            for (int j = start; j < sortedCandidates.size(); j++) {
                // 如果当前值大于目标值，则终止
                if (sortedCandidates[j] > target) {
                    break;
                }
                // 跳过重复元素
                if (j > 0 && sortedCandidates[j] == sortedCandidates[j - 1] &&
                    !used[j - 1]) {
                    continue;
                }

                path.emplace_back(sortedCandidates[j]);
                used[j] = true;
                dfs(dfs, j + 1, target - sortedCandidates[j]);
                used[j] = false;
                path.pop_back();
            }
        };

        dfs(dfs, 0, target);
        return res;
    }
};
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
35
36
37
38
39
40

# 组合总和 III (opens new window)（可重复选中）

# 排列

排列问题需要递归遍历所有元素，且判断元素是否被使用

# 全排列 (opens new window) （无重复元素）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

func permute(nums []int) [][]int {
    var res [][]int
    var path []int
    var st   []bool

    res, path = make([][]int, 0), make([]int, 0, len(nums))
    st = make([]bool, len(nums))

    var dfs func(cur int) 
    dfs = func(cur int) {
        if cur == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
        }
        for i:=0; i < len(nums); i++ {
            if !st[i] {
                path = append(path, nums[i])
                st[i] = true
                dfs(cur+1)
                st[i] = false
                path = path[:len(path)-1]
            }
        }
    }

    dfs(0)
    return res
}
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
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        vector<int> path(n);
        vector<bool> st(n);

        auto dfs = [&] (auto&& dfs, int cur) {
            if (cur == n) {
                res.emplace_back(path);
                return;
            }
            for (int i=0; i<n; i++) {
                if (!st[i]) {
                    path[cur] = nums[i];
                    st[i] = true;
                    dfs(dfs, cur+1);
                    st[i] = false;
                }
            }
        };
        dfs(dfs, 0);
        return res;
    }
};
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

# 全排列 II (opens new window)（含重复元素）

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

func permuteUnique(nums []int) [][]int {
    res, path := make([][]int, 0), make([]int, 0, len(nums))
    st := make([]bool, len(nums))
    sort.Ints(nums)

    var dfs func() 
    dfs = func() {
        if len(path) == len(nums) {
            tmp := make([]int, len(path)) 
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i:=0; i < len(nums); i++ {
            if i!=0 && nums[i] == nums[i-1] && !st[i-1] {
                continue
            }
            if !st[i] {
                path = append(path, nums[i])
                st[i] = true
                dfs()
                st[i] = false
                path = path[:len(path)-1]
            }
        }
    }

    dfs()
    return res
}
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

# 分割

# 分割回文串 (opens new window)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。 示例 1： 输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

func partition(s string) [][]string {
	n := len(s)
	dp := make([][]bool, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
        for j := 0; j <= i; j++ {
			dp[i][j] = true
		}
	}

	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
		}
	}

	res := [][]string{}
	split := []string{}
	var dfs func(i int)
	dfs = func(i int) {
		if i == n {
            tmp := make([]string, len(split))
            copy(tmp, split)
			res = append(res, tmp)
			return
		}
		for j := i; j < n; j++ {
			if dp[i][j] {
				split = append(split, s[i:j+1])
				dfs(j + 1)
				split = split[:len(split)-1]
			}
		}
	}
	dfs(0)
	return res
}
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
35
36
37
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> res;
        vector<string> split;
        vector<vector<bool>> f(n, vector<bool>(n, true));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; j++) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        auto dfs = [&](auto dfs, int i) {
            if (i == n) {
                res.emplace_back(split);
                return;
            }

            for (int j = i; j < n; j++) {
                if (f[i][j]) {
                    split.emplace_back(s.substr(i, j - i + 1));
                    dfs(dfs, j + 1);
                    split.pop_back();
                }
            }
        };

        dfs(dfs, 0);
        return res;
    }
};
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

# 复原 IP 地址 (opens new window)

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1： 输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

# 子集

两种情况，给定数组

  1. 不包含重复元素
  2. 包含重复元素

# 子集 (opens new window)（无重复元素）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

func subsets(nums []int) [][]int {
    res, path := make([][]int, 0), make([]int, 0, len(nums))

    var dfs func(start int) 
    dfs = func(start int) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)

        for i:=start; i<len(nums); i++ {
            path = append(path, nums[i])
            dfs(i+1)
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 子集 II (opens new window)（有重复元素）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。 输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

func subsetsWithDup(nums []int) [][]int {
    res, path := make([][]int, 0), make([]int, 0, len(nums))
    used := make([]bool, len(nums))

    var dfs func(start int) 
    dfs = func(start int) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)

        for i:=start; i<len(nums); i++ {
            if i!=0 && nums[i-1] == nums[i] && used[i-1] == false {
                continue
            }
            path = append(path, nums[i])
            used[i] = true
            dfs(i+1)
            used[i] = false
            path = path[:len(path)-1]
        }
    }

    sort.Ints(nums)
    dfs(0)
    return res
}
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

# 棋盘

# N 皇后 (opens new window)

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n_ _皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

func solveNQueens(n int) [][]string {
    col := make([]int, n)   //每一行中，皇后放的位置
    onPath := make([]bool, n)  //该列是否已放皇后
    diag1, diag2 := make([]bool, 2*n-1), make([]bool, 2*n-1) //该对角是否已放皇后
    res := [][]string{}
    var dfs func(int)
    dfs = func(r int) {
        if r == n {          //最后一行已经填满，收割结果即可
            board := make([]string, n)
            for i, c := range col {
                board[i] = strings.Repeat(".", c) + "Q" + strings.Repeat(".", n-1-c)
            }
            res = append(res, board)
            return
        }
        for c, on := range onPath {
            rc := r - c + n - 1
            if !on && !diag1[r+c] && !diag2[rc] {
                col[r] = c
                onPath[c], diag1[r+c], diag2[rc] = true, true, true
                dfs(r+1)
                onPath[c], diag1[r+c], diag2[rc] = false, false, false
            }
        }
    }
    dfs(0)    //第一行开始排位置
    return res
}
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

# 解数独 (opens new window)

数独的解法需** 遵循如下规则**：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

func solveSudoku(board [][]byte) {
	var backtracking func(board [][]byte) bool
	backtracking = func(board [][]byte) bool {
		for i := 0; i < 9; i++ {
			for j := 0; j < 9; j++ {
				//判断此位置是否适合填数字
				if board[i][j] != '.' {
					continue
				}
				//尝试填1-9
				for k := '1'; k <= '9'; k++ {
					if isvalid(i, j, byte(k), board) == true { //如果满足要求就填
						board[i][j] = byte(k)
						if backtracking(board) == true {
							return true
						}
						board[i][j] = '.'
					}
				}
				return false
			}
		}
		return true
	}
	backtracking(board)
}

//判断填入数字是否满足要求
func isvalid(row, col int, k byte, board [][]byte) bool {
	for i := 0; i < 9; i++ { //行
		if board[row][i] == k {
			return false
		}
	}
	for i := 0; i < 9; i++ { //列
		if board[i][col] == k {
			return false
		}
	}
	//方格
	startrow := (row / 3) * 3
	startcol := (col / 3) * 3
	for i := startrow; i < startrow+3; i++ {
		for j := startcol; j < startcol+3; j++ {
			if board[i][j] == k {
				return false
			}
		}
	}
	return true
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
编辑 (opens new window)
上次更新: 2024/09/13, 11:59:12
贪心算法
单调栈

← 单调栈→

最近更新
01
ceph分布式存储-对象存储(RGW)搭建
10-27
02
ceph分布式存储-集群客户端连接
10-27
03
ceph分布式存储-管理crushmap
10-27
更多文章>
Theme by Vdoing