[Algorithm] Shortest Addition Chains (Backtracking)

http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

 

An addition chain for an integer n is an increasing sequence of integers that starts with 1 and ends with n, such that each entry after the first is the sum of two earlier entries. 
More formally, the integer sequence x0 < x1 < x2 < ··· < x` is an addition chain for n if and only if 
 • x0 = 1, 
 • xl = n, and 
 • for every index k > 0, there are indices i ≤ j < k such that xk = xi + xj 
The length of an addition chain is the number of elements minus 1; we don’t bother to count the first entry. For example, ⟨1, 2, 3, 5, 10, 20, 23, 46, 92, 184, 187, 374⟩ is an addition chain for 374 of length 11.  
 
(a) Describe a recursive backtracking algorithm to compute a minimum length addition chain for a given positive integer n.

 

<Backtracking Code>

#include<iostream>
#include<vector>
using namespace std;

int N;
int Min = 10000000; // 1000만
int result;
vector<int> v;
vector<int> ans;

void backtracking(int k)
{
	if (v.size() >= Min) return;

	if (k == N)
	{
		if (v.size() < Min)
		{
			Min = v.size();
			ans.clear();
			for (int i = 0; i < v.size(); i++) ans.push_back(v[i]);
		}
	}
		
	for (int i = v.size() - 1; i >= 0; i--)
	{
		if (k + v[i] <= N)
		{
			v.push_back(k + v[i]);
			backtracking(k + v[i]);
			v.pop_back();
		}
	}
}

int main()
{
	cin >> N;
	v.push_back(1);
	backtracking(1);
	
	cout << "chain : ";
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << " ";
	cout << "\nlength : " << ans.size() - 1 << '\n';
}

 

Result