Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7]
and target 7
,
[ [7], [2, 2, 3]]
思路:实现其实很简单,整除就是满足的,不整除做减法,偏移重复上述操作, (我没有追求输出结果)
package mainimport ( "fmt")func test_array_contain_elements(arr []int, dest_val int) { length := len(arr) for i := length - 1; i > 0; i-- { var tmp_arr []int tmp_val := dest_val for j := i; j >= 0; { left_val := tmp_val % arr[j] if left_val == 0 { element_num := tmp_val / arr[j] for element_num > 0 { tmp_arr = append(tmp_arr, arr[j]) element_num-- } fmt.Printf("%v\n", tmp_arr) break } else { tmp_val = tmp_val - arr[j] tmp_arr = append(tmp_arr, arr[j]) j-- if tmp_val < arr[j] { break } } } }}func main() { arr := []int{2, 3, 6, 7} test_array_contain_elements(arr, 7)}
输出结果:
[7]
[3 2 2]