Commite7ba8de

authored

Merge pull requestyoungyangyang04#488 from X-shuffle/master

增加 0047.全排列II go版本

2 parents1e6a9b8 +be87481 commite7ba8deCopy full SHA for e7ba8de

File tree

1 file changed

+39

-1

lines changed

problems
- 0047.全排列II.md

1 file changed

+39

-1

lines changed

`‎problems/0047.全排列II.md`

Lines changed: 39 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -296,7 +296,45 @@ var permuteUnique = function (nums) {`
`296`	`296`	`};`
`297`	`297`
`298`	`298`	```
`299`		`-`
	`299`	`+Go：`
	`300`	`+回溯+本层去重+下层去重`
	`301`	+```golang
	`302`	`+funcpermuteUnique(nums []int) [][]int {`
	`303`	`+varsubRes []int`
	`304`	`+varres [][]int`
	`305`	`+ sort.Ints(nums)`
	`306`	`+used:=make([]bool,len(nums))`
	`307`	`+backTring(nums,subRes,&res,used)`
	`308`	`+return res`
	`309`	`+}`
	`310`	`+funcbackTring(nums,subRes []int,res *[][]int,used []bool){`
	`311`	`+iflen(subRes)==len(nums){`
	`312`	`+tmp:=make([]int,len(nums))`
	`313`	`+copy(tmp,subRes)`
	`314`	`+ res=append(res,tmp)`
	`315`	`+return`
	`316`	`+ }`
	`317`	`+// used[i - 1] == true，说明同一树支candidates[i - 1]使用过`
	`318`	`+// used[i - 1] == false，说明同一树层candidates[i - 1]使用过`
	`319`	`+fori:=0;i<len(nums);i++{`
	`320`	`+if i>0&&nums[i]==nums[i-1]&&used[i-1]==false{//当本层元素相同且前一个被使用过，则继续向后找（本层去重）`
	`321`	`+continue`
	`322`	`+ }`
	`323`	`+//到达这里有两种情况：1.该层前后元素不同；2.该层前后元素相同但该层没有使用过`
	`324`	`+//所以只能对该层没有被使用过的抽取`
	`325`	`+if used[i]==false{`
	`326`	`+//首先将该元素置为使用过（即同一树枝使用过），下一层的元素就不能选择重复使用过的元素（下层去重）`
	`327`	`+ used[i]=true`
	`328`	`+ subRes=append(subRes,nums[i])`
	`329`	`+backTring(nums,subRes,res,used)`
	`330`	`+//回溯`
	`331`	`+//回溯回来，将该元素置为false，表示该元素在该层使用过`
	`332`	`+ used[i]=false`
	`333`	`+ subRes=subRes[:len(subRes)-1]`
	`334`	`+ }`
	`335`	`+ }`
	`336`	`+}`
	`337`	+```
`300`	`338`
`301`	`339`
`302`	`340`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commite7ba8de

File tree

1 file changed

1 file changed

`‎problems/0047.全排列II.md`

0 commit comments