回溯算法是一种搜索算法，适用于根据一组给定的条件来搜索问题的解。
例13－4 从1到X中选出N个数字，排成一列，相邻两数不能相同，求所有可能的排法。每个数可以选用零次、一次或多次。例如，当N＝3、X＝3时，排法有12种:121、123、131、132、212、213、231、232、312、313、321、323。
分析:以N＝3，X＝3为例，这个问题的每个解可分为三个部分:第一位，第二位，第三位。先写第一位，第一位可选1、2或3，根据从小到大的顺序，此处选1；那么，为了保证相邻两数不同，第二位就只能选2或3了，此时选2；最后，第三位可以选1或3，则选1；这样就得到了第一个解“121”。然后，将第三位变为3，就得到了第二个解“123”。此时，第三位已经不能再取其他值了，于是返回第二位，看第二位还能变为什么值。第二位可以变为3，于是可以在“13”的基础上再给第三位赋予不同的值1和2，得到第三个解“131”和“132”。此时第二位也已经不能再取其他值了，于是返回第一位，将它变为下一个可取的值2，然后按顺序变换第二位和第三位，得到“212”“213”“231”“232”。这样，直到第一位已经取过了所有可能的值，并且将每种情况下的第二位和第三位都按上述思路取过一遍，得到该问题的全部解。(www.xing528.com)
由以上过程可以看出，回溯法的思路是:问题的每个解都包含N部分，先给出第一部分，再给出第二部分……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。
程序如下:
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
