数据结构与算法

1 数字排列组合

1.1 描述

用 Golang 实现，将四个数进行排列组合。

1.2 题目

有 1、2、3、4 这四个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

1.3 题目解决思路

可填在百位、十位、个位的数字都是 1、2、3、4。组成所有的排列后再去掉不满足条件的排列。

1.4 代码具体实现

  1.固定层数for循环：暴力枚举算法

  适用场景：题目位数固定（本题固定三位数）；

  数据范围极小，只求快速通过。属于专用算法

package main
import (
	"fmt"
)
func main() {
	totalCount := 0
	/*以下为三重循环*/
	for i := 1; i < 5; i++ {
		for j := 1; j < 5; j++ {
			for k := 1; k < 5; k++ {
				/*确保 i 、j 、k 三位互不相同*/
				if i != k && i != j && j != k {
					totalCount++
					fmt.Println("第", totalCount, "方案", "i =", i, "j =", j, "k =", k)
				}
			}
		}
	}
	
	fmt.Println("共", totalCount, "种方案")
}

算法思路：回溯法（全排列选取3个元素）
核心算法：回溯（深度优先搜索DFS），从4个数字中选出3个进行排列，保证元素不重复，这是通用排列算法，数字数量、选取位数任意修改都可以复用。
选择一个未使用数字放入当前位置
标记该数字已被使用
递归填充下一位
递归回溯，撤销标记，尝试其他数字
凑够3位即为一组合法解
Go完整回溯代码
package main

import "fmt"

// 回溯函数
func backtrack(nums []int, used []bool, path []int, length int, result *[][]int) {
	// 终止条件：path长度等于3，找到一组解
	if len(path) == length {
		temp := make([]int, len(path))
		copy(temp, path)
		*result = append(*result, temp)
		return
	}

	for i := 0; i < len(nums); i++ {
		// 数字已经被选用，跳过
		if used[i] {
			continue
		}
		used[i] = true          // 选择
		path = append(path, nums[i])
		backtrack(nums, used, path, length, result)
		path = path[:len(path)-1] // 回溯撤销选择
		used[i] = false
	}
}

// 获取排列结果
func permutation(nums []int, pickNum int) [][]int {
	var result [][]int
	used := make([]bool, len(nums))
	backtrack(nums, used, []int{}, pickNum, &result)
	return result
}

func main() {
	nums := []int{1, 2, 3, 4}
	res := permutation(nums, 3)

	fmt.Println("所有无重复三位数组合：")
	count := 0
	for _, v := range res {
		num := v[0]*100 + v[1]*10 + v[2]
		fmt.Printf("%d ", num)
		count++
	}
	fmt.Printf("\n总数量：%d\n", count)
}
算法复杂度分析
时间复杂度：A_n^k = \dfrac{n!}{(n-k)!}，本题n=4，k=3，运算24次。
空间复杂度：O(n)，used数组和递归栈开销。
执行输出
所有无重复三位数组合：
123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432
总数量：24
对比说明
三层for循环属于暴力枚举，只适用于固定3位，属于特例写法。
回溯DFS是标准排列算法，属于通用解法，选2位、选4位、任意数组都能直接使用，面试算法标准答案。
如果你需要，我可以补充去重版本（存在重复数字时使用）。