去重相关题目

题目1：有重复字符串的排列组合

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

输入：S = "qqe" 输出：["eqq","qeq","qqe"] 示例2:

输入：S = "ab" 输出：["ab", "ba"] 提示:

字符都是英文字母。 字符串长度在[1, 9]之间。

力扣

https://leetcode.cn/problems/permutation-ii-lcci/

• 解决思路：

只要确保，向下遍历的每一层不会取同样的值即可避免重复，从而避免重复，不过需要提前对S进行字符排序

func permutation(S string) []string {
    // 重复版回溯增加的处理无非就是同一个位置不能同时取同一个值
    // 因为这样会导致出现重复结果
    // 先对字符串进行排序，使所有相同的字符处在相同的位置
    var ans []string
    n := len(S)
    s := []byte(S)
    sort.Slice(s,func(i,j int)bool{
        return s[i]<s[j]
    })
    var dfs func(i int)
    dfs = func(i int){
        if i==n{
            ans=append(ans,string(s))
            return
        }
        vis := make(map[byte]bool)
        for j:=i;j<n;j++{
            // 利用hash表记录当层已经取过的值，以防重复在相同层取重复值
            if vis[s[j]]{
                continue
            }
						// 每个i位置的字符都可以与其右边的字符进行交换
						// 从而构造全排列序列
            vis[s[j]]=true
            s[i],s[j]=s[j],s[i]
            dfs(i+1)
            s[i],s[j]=s[j],s[i]
        }
    }
    dfs(0)
    return ans
}

经典题目

题目1：解出n对括号的不同组合序列

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

力扣

https://leetcode.cn/problems/bracket-lcci

• tips：这道题之前在面试金山云的时候手撕过🤣🤣🤣

• 方法一：利用剩余未使用左右括号数

func generateParenthesis(n int) []string {
	// my solution：可以使用回溯，最左的左括号按照每次隔着
	// n-1,n-2...0个左括号的格式进行构建，然后递归下去，递归到底后回溯
	var ans []string
	// leftCount,rightCount 分别记录剩余的左括号和右括号数
	var dfs func(lw int, leftCount int, rightCount int, path []byte)
	dfs = func(lw int, leftCount int, rightCount int, path []byte) {
		if leftCount == 0 && rightCount == 0 {
			ans = append(ans, string(path))
			return
		}
		// 每一层，左侧括号隔着的左括号共有0-leftCount-1种
		// 左写3，剩余0，右要全写
		// 左写2，剩余1，右可以1，也可以直接写2
		// 左写1，剩余2，右必须写1
		// 然后按照上述步骤递归
		for i := leftCount; i > 0; i-- {
			// 这一步必须肯定写入了左括号，则下一步必须写入右括号
			lw += i
			for j := 0; j < i; j++ {
				path = append(path, '(')
			}
			// 右边可以写1到已经写的左括号数个右括号
            // k的数必须小于等于左边写入左括号数再减去左边已经写的右括号数
            // min(lw-(n-rightCount), rightCount)是为了防止最后出现右括号未使用完毕的情况
			for k := min(lw-(n-rightCount), rightCount); k > 0; k-- {
				for l := 0; l < k; l++ {
					path = append(path, ')')
				}
				dfs(lw, leftCount-i, rightCount-k, path)
				path = path[:len(path)-k]
			}
			lw -= i
			path = path[:len(path)-i]
		}
	}
	dfs(0, n, n, []byte{})
	return ans
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

• 方法二：利用已使用左右括号数

func generateParenthesis(n int) []string{
    // 方法二：思路更加清晰的回溯,利用已经使用左右括号数来解
    var ans []string
    var dfs func(leftCount,rightCount int,path []byte)
    dfs = func(leftCount,rightCount int,path []byte){
        if len(path)==n<<1{
            ans=append(ans,string(path))
            return
        }
        if leftCount<n{
            path=append(path,'(')
            dfs(leftCount+1,rightCount,path)
            path=path[:len(path)-1]
        }
        if rightCount<leftCount{
            path=append(path,')')
            dfs(leftCount,rightCount+1,path)
            path=path[:len(path)-1]
        }
    }
    dfs(0,0,[]byte{})
    return ans
}