LC031. Next Permutation

1, Title

An arrangement of an integer array is to arrange all its members in sequence or linear order.

For example, arr = [1,2,3], the following can be regarded as the arrangement of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers refers to the next lexicographically ordered permutation of its integers. More formally, if all permutations of an array are arranged in a container from small to large according to their dictionary order, the next permutation of the array is the one behind it in the ordered container. If there is no next larger permutation, the array must be rearranged to the least lexicographically ordered permutation (that is, its elements are arranged in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
The next permutation of arr = [3,2,1] is [1,2,3], because there is no permutation with larger dictionary order in [3,2,1].
Give you an integer array nums and find the next arrangement of nums.

It must be modified in place and only additional constant space is allowed.

Example 1:

Input: num = [1,2,3]
Output: [1,3,2]
Example 2:

Input: num = [3,2,1]
Output: [1,2,3]
Example 3:

Input: num = [1,1,5]
Output: [1,5,1]

Tips:

1 <= nums.length <= 100
0 <= nums[i] <= 100

2, Implementation method

This brother's solution is clearer than anything Force bucklehttps://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

func main()  {
	nums:=[]int{1,2,3}
	nextPermutation(nums)
	fmt.Println(nums)
}

func nextPermutation(nums []int){
	n:=len(nums)
	if n==1{
		return
	}
	i,j,k:=n-2,n-1,n-1
	// Find ascending pairs
	// find: A[i]<A[j]
	for i>=0&&nums[i]>=nums[j]{
		i--
		j--
	}
	if i >= 0 { // Not the last permutation
		// find: A[i]<A[k]
		for nums[i] >= nums[k] {
			k--
		}
		// swap A[i], A[k]
		nums[i], nums[k] = nums[k], nums[i]
	}

	// reverse A[j:end]
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

 

LeetCode039. Combination Sum

1, Title

Give you an array of integers with no duplicate elements, @ candidates, and a target integer, @ target. Find out all the different combinations of numbers and targets in ， candidates ， and return them in the form of a list. You can return these combinations in any order.

The same number in candidates can be selected repeatedly without limit. If the selected number of at least one number is different, the two combinations are different.  

For a given input, ensure that the number of different combinations with sum target is less than 150.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
 Output: [[2,2,3], [7]]
Explanation:
2 and 3 can form a set of candidates, 2 + 2 + 3 = 7. Note 2 can be used multiple times.
7 is also a candidate, 7 = 7.
There are only two combinations.
Example 2:

Input: candidates = [2,3,5], target = 8
 Output: [[2,2,2,2], [2,3,3], [3,5]]
Example 3:

Input: candidates = [2], target = 1
 Output: []
 

Tips:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
 Each element in the candidate is different from each other
1 <= target <= 500

2, Implementation method

Method 1: backtracking + pruning

If repetition is allowed:

//Time complexity: O(S), where S is the sum of the lengths of all feasible solutions. O(n × 2^n) is a relatively loose upper bound, but the actual operation is far less than this upper bound.
//Space complexity: O(target). In addition to the answer array, the space complexity depends on the recursive stack depth. In the worst case, the recursive O(target) layer is required.
//Optimization method: pruning -- sum + candidates [i] < = target

func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var path []int
	backtracking(&res,path,candidates,target,0,0)
	return res
}

func backtracking(res *[][]int,path []int,candidates []int,target int,startindex,sum int){
	// End condition
	if sum==target{
		temp:=make([]int,len(path))
		copy(temp,path)
		*res=append(*res,temp)
	}
	if sum>target{
		return
	}
	// After optimization
	for i:=startindex;i<len(candidates)&&sum + candidates[i] <= target;i++{
		// Before optimization
		//for i:=startindex;i<len(candidates);i++{
		sum+=candidates[i]
		path=append(path,candidates[i])
		backtracking(res,path,candidates,target,i,sum)
		sum-=candidates[i]
		path=path[:len(path)-1]
	}
	return
}

If repetition is not allowed: (LC040)

Add a map or array uesd to record whether it is used in this branch. The key is the subscript of candidates

Sorting is required before backtracking. If the current value is the same as the previous value and the previous value has been taken, it can be taken

Examples (1,1);

Take only the first 1 and only the second 1. Although it is not the same 1, the path will repeat, (1, x, x), (1, x, x);

So if you want to take the second one, you have to take both ones. The first one has no value, and the second one cannot be taken, (1, 1, x);

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

//Time complexity: O(S), where S is the sum of the lengths of all feasible solutions. O(n × 2^n) is a relatively loose upper bound, but the actual operation is far less than this upper bound.
//Spatial complexity: O(n). In addition to the answer array, we need O(n) space to store used.
//Optimization method: pruning -- sum + candidates [i] < = target

func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var path []int
	sort.Ints(candidates)
	used:=make(map[int]bool)
	backtracking(&res,path,candidates,target,0,0,used)
	return res
}

func backtracking(res *[][]int,path []int,candidates []int,target int,startindex,sum int,used map[int]bool){
	// End condition
	if sum==target{
		temp:=make([]int,len(path))
		copy(temp,path)
		*res=append(*res,temp)
	}
	if sum>target{
		return
	}
	// After optimization
	for i:=startindex;i<len(candidates)&&sum + candidates[i] <= target;i++{
	// Before optimization
	//for i:=startindex;i<len(candidates);i++{
		// Check whether it is the same as the previous one
		if i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false{
			continue
		}
		used[i]=true
		sum+=candidates[i]
		path=append(path,candidates[i])
		// startIndex changes to i+1, starting with the next element
		backtracking(res,path,candidates,target,i+1,sum,used)
		sum-=candidates[i]
		path=path[:len(path)-1]
		used[i]=false
	}
	return
}

 

LC078. Subset Subsets

1, Title

Give you an integer array {nums. The elements in the array are different from each other. Returns all possible subsets (power sets) of the array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

 

Example 1:

Input: num = [1,2,3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Example 2:

Input: num = [0]
Output: [[], [0]]
 

Tips:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
 All elements in nums are different from each other

2, Solution

Method 1: backtracking

func main()  {
	nums:=[]int{1,2,3}
	fmt.Println(Subsets(nums))
}

func Subsets(nums []int) [][]int {
	var res [][]int
	var path []int
	backtracking(&res,path,nums,0)
	return res
}

func backtracking(res *[][]int,path []int,nums []int,startindex int){
	// Pay attention to the application length
	temp:=make([]int,len(path))
	copy(temp,path)
	*res=append(*res,temp)
	for i:=startindex;i<len(nums);i++{
		path=append(path,nums[i])
		// startindex is the current subscript + 1
		backtracking(res,path,nums,i+1)
		path=path[:len(path)-1]
	}
	return
}