The title

Take any n elements from a string of arbitrary length and print all possible combinations of those elements. Prerequisite: Ensures that the input string has no duplicate elements

Example:

Input characters’ ABC ‘, take two arbitrary element output: ‘ab’, ‘ac’, ‘the BC’, ‘ba’, ‘ca’, ‘cb’

Train of thought

The problem can be broken down into two steps:

  1. Find all subsets of N of M elements
  2. Find the total permutations of N non-repeating elements

After splitting it, there are actually two more basic problems, both of which have similar problems in Leetcode. Here is my idea.

Find all subsets of N of M elements

This is a recursive idea. For example, if you take any 3 of 5, you can split it into

  1. You take the first element, and then you have to take 2 of the remaining 4
  2. Take the first of the four remaining, and then take the first of the three remaining
  3. At this point, you just need to take out all three in order

So this is a recursion, and the recursion ends with n===1. Let’s start with some code:

function picked(str: string, m: number, outPut: string[]) {
  if (m == 1) {
    Array.from(str).forEach((s) = > {
      console.log([...outPut, s]);
    });
    return;
  }
  outPut.push(str[0]);
  str = str.slice(1);
  m = m - 1;
  picked(str, m, outPut);
}
picked('abcdef'.3[]),Copy the code

Run it and find a problem that only outputs all possibilities starting with ‘a’. Let’s think about the problem with our recursion: each time we take the first element of the remaining element, we need to run again starting with B, and so on:

function getPicked(str: string, m: number) {
  for (let i = 0; i < str.length - m + 1; i++) {
    letoutPut = []; picked(str.slice(i), m, outPut); }}Copy the code

Notice here that we’re not going to go through ‘bcdef’ all at once, because when you get to ‘d’, there’s only one possibility left: ‘def’. I don’t have to go through it. That’s it

This is a fairly naive algorithm, and you can actually extract it again.

Find the total permutations of N non-repeating elements

Similar to the previous problem, if you have a string ‘abcd’, think about its arrangement:

  1. If ‘a’ is fixed, then we are taking the complete permutation of ‘BCD’
  2. If ‘b’ is also fixed, then you’re just looking for all the permutations of ‘CD’, and that’s easy, there’s only two of them

Let’s try to write the logic

function sort(str: string, outPut: string[]) {
  if (str.length == 2) {
    console.log([...outPut, str[0], str[1]]);
    console.log([...outPut, str[1], str[0]]);
    return;
  }
  outPut.push(str[0]);
  str = str.slice(1);
  sort(str, outPut);
}
sort('abc'[]),Copy the code

The same situation as the previous problem occurs, except for the case that begins with a. Similarly, let’s do another traversal:

function getSort(str: string) {
  for (let i = 0; i < str.length; i++) {
    let outPut = [];
    letsubStr = str.slice(i) sort(subStr, outPut); }}Copy the code

It feels ok, but there is a problem with running it, so every time you iterate, the string gets shorter, it becomes a child arrangement, not a full arrangement. If you think about it, you should actually append the elements that you’ve already traversed to the end of the substring to form a new string. The new string has the same length as the original string.

unction getSort(str: string) {
  for (let i = 0; i < str.length; i++) {
    let outPut = [];
    // We have changed it here
    let subStr = str.slice(i) + str.slice(0, i); sort(subStr, outPut); }}Copy the code

OK.

review

I looked it up, and it’s called a backtracking algorithm. Backtracking is cleaner, but it’s a little harder to understand. And you can follow this idea and implement it. Once implemented, look at the backtracking algorithm, and it becomes easier to understand.