What is Backtracking

An algorithm that explores combinations that satisfy specified constraints.

It can be used when exploring all unique combinations (nCr).

Implementation

The source code is as follows.

This process retrieves N unique subsequences from a given array. Below is an example of 4C3.

package main

import "fmt"

func backtrack(rslt *[][]int, tmp []int, items []int, start int, k int) {
	if k == 0 {
		combination := make([]int, len(tmp))
		copy(combination, tmp)
		*rslt = append(*rslt, combination)
		return
	}

	for i := start; i < len(items); i++ {
		tmp = append(tmp, items[i])
		backtrack(rslt, tmp, items, i+1, k-1)
		tmp = tmp[:len(tmp)-1]
	}
}

func get(items []int, k int) [][]int {
	rslt := [][]int{}
	tmp := []int{}
	backtrack(&rslt, tmp, items, 0, k)
	return rslt
}

func main() {
	items := []int{1, 2, 3, 4}
	k := 3
	combination := get(items, k)
	fmt.Println(combination)
}

[[1 2 3] [1 2 4] [1 3 4] [2 3 4]]

In the recursive process, it may feel like the brain's memory is about to burst, but thinking of the data as a tree structure makes it clearer.

When data consisting of 1, 2, 3, and 4 is passed, consider what results can be obtained for k from 0 to 4.

k = 0
N/A

k = 1
1  2  3  4

k = 2

	   1      2    3
	  / | \   / \   |
	 2  3  4 3   4  4

k = 3

		   1     2
		  / \    |
		 2   3   3
		 / \  |   |
		3  4  4   4

k = 4
1
2
3
4