【回溯法】列举一个n维数组中所有元素的索引值

之前面试遇到一道算法题，题目描述如下：

1. 题目描述

已知一个n维数组，其维度为i1, i1,… ,in，其中in为正整数， 用C语言表示为：dimensions = {i1, i2, …, in}, 编写函数，列举出数组中所有元素的索引值。

例1：

input = {2,3}
output = {
		{1,1}, {1,2}, {1,3},
		{2,1}, {2,2}, {2,3}
}

例2：

	input = {2,4,3}
	output = {
		{1,1,1}, {1,1,2}, {1,1,3},
		{1,2,1}, {1,2,2}, {1,2,3},
		{1,3,1}, {1,3,2}, {1,3,3},
		{1,4,1}, {1,4,2}, {1,4,3},

		{2,1,1}, {2,1,2}, {2,1,3},
		{2,2,1}, {2,2,2}, {2,2,3},
		{2,3,1}, {2,3,2}, {2,3,3},
		{2,4,1}, {2,4,2}, {2,4,3},
	}

注意：n 的个数由输入参数决定，能够适应任意纬度，不可硬编码在算法中。

2. 编码实现

这道题跟经典的八皇后问题类似，可以用回溯法来解决。从第1维开始依次确定各个维度的取值，取到第n维那么保存中间结果。编码如下：

#include <iostream>
#include <sstream>
#include <vector>
#include <string.h>
using namespace std;
void backtrace(const vector<int>& input, vector<int>* temp , int index, int size, vector<vector<int> >* output);
void EnumerateAllIndex(const vector<int>& input, vector<vector<int> >* output)
{
	int size = input.size();
	int i = 0;
	vector<int> temp;
	backtrace(input, &temp, 0, size, output);
}

// 回溯法，从第0个元素开始依次取下一个索引,取满则存储中间结果
void backtrace(const vector<int>& input, vector<int>* temp , int index, int size, vector<vector<int> >* output) 
{
	if (index == size) {
		output->push_back(*temp);
		return ;
	}
	int i = 0;
	for (i = 1; i <= input[index]; i++) {
		temp->push_back(i);
		backtrace(input, temp, index + 1, size, output);
		temp->pop_back();
	}
}

void PrintAllIndex(vector<vector<int> >& index_list)
{
    // 此处答题：
	int i, j;
	cout << "{" << endl;
	for (i = 0; i < index_list.size(); i++) {
		cout << "{";
		for (j = 0; j < index_list[i].size(); j++) {
			cout << index_list[i][j];
			if (j != index_list[i].size() - 1) {
				cout << ",";
			} else {
				cout << "},"<<endl;
			}	
		}
	}
	cout << "}";
}

//////////////////////////////////////////////////////////////////////////
// Main
//////////////////////////////////////////////////////////////////////////
int main()
{
    cout << "Case1..." << endl;
    vector<int> dims;
    dims.push_back(2);
    dims.push_back(4);
    dims.push_back(3);
    vector<vector<int> > index_list;
    EnumerateAllIndex(dims, &index_list);
    PrintAllIndex(index_list);
	return 0;
}

3.运行结果

以上代码运行结果：