/** www.techiedelight.com/find-permutations-given-string/ */
class AllStringPermutations {
 
	public static void main(String[] args) {
		String s = "ABC";
 
		findAndPrintPermutations("", s, s.length());
 
		System.out.println();
		char[] c = {'A', 'B', 'C'};
		findAndPrintPermutationsCharArrayAlternative(c, 0);
	}
 
	private static void findAndPrintPermutations(String candidate, String remaining, int counter) {
		if (counter == 0) {
			System.out.println(candidate);
			return;
		}
 
		// Given that in Java Strings are immutable this is not really backtracking but 
		// the principle is similar.
		// For a similar solution to C++ check findAndPrintPermutationsCharArrayAlternative 
		// which uses a char [] 
		for (int i = 0; i < remaining.length(); i++) {
			String newCandidate = candidate + remaining.charAt(i);
			String newRemaining =
				remaining.substring(0, i) + remaining.substring(i + 1, remaining.length());
 
			findAndPrintPermutations(newCandidate, newRemaining, counter - 1);
		}
	}
 
	private static void findAndPrintPermutationsCharArrayAlternative(char[] c, int currentIndex) {
		if (currentIndex == c.length - 1) {
			for (int i = 0; i < c.length; i++) {
			System.out.print(c[i]);
			}
			System.out.println();
			return;
		}
 
		for (int i = currentIndex; i < c.length; i++) {
			swap(c, currentIndex, i);
			findAndPrintPermutationsCharArrayAlternative(c, currentIndex + 1);
			swap(c, currentIndex, i);
		}
	}
 
	private static void swap(char[] c, int x, int y) {
		char temp = c[x];
		c[x] = c[y];
		c[y] = temp;
	}
}

LyoqIHd3dy50ZWNoaWVkZWxpZ2h0LmNvbS9maW5kLXBlcm11dGF0aW9ucy1naXZlbi1zdHJpbmcvICovCmNsYXNzIEFsbFN0cmluZ1Blcm11dGF0aW9ucyB7CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCVN0cmluZyBzID0gIkFCQyI7CgoJCWZpbmRBbmRQcmludFBlcm11dGF0aW9ucygiIiwgcywgcy5sZW5ndGgoKSk7CgoJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJCWNoYXJbXSBjID0geydBJywgJ0InLCAnQyd9OwoJCWZpbmRBbmRQcmludFBlcm11dGF0aW9uc0NoYXJBcnJheUFsdGVybmF0aXZlKGMsIDApOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZmluZEFuZFByaW50UGVybXV0YXRpb25zKFN0cmluZyBjYW5kaWRhdGUsIFN0cmluZyByZW1haW5pbmcsIGludCBjb3VudGVyKSB7CgkJaWYgKGNvdW50ZXIgPT0gMCkgewoJCQlTeXN0ZW0ub3V0LnByaW50bG4oY2FuZGlkYXRlKTsKCQkJcmV0dXJuOwoJCX0KCgkJLy8gR2l2ZW4gdGhhdCBpbiBKYXZhIFN0cmluZ3MgYXJlIGltbXV0YWJsZSB0aGlzIGlzIG5vdCByZWFsbHkgYmFja3RyYWNraW5nIGJ1dCAKCQkvLyB0aGUgcHJpbmNpcGxlIGlzIHNpbWlsYXIuCgkJLy8gRm9yIGEgc2ltaWxhciBzb2x1dGlvbiB0byBDKysgY2hlY2sgZmluZEFuZFByaW50UGVybXV0YXRpb25zQ2hhckFycmF5QWx0ZXJuYXRpdmUgCgkJLy8gd2hpY2ggdXNlcyBhIGNoYXIgW10gCgkJZm9yIChpbnQgaSA9IDA7IGkgPCByZW1haW5pbmcubGVuZ3RoKCk7IGkrKykgewoJCQlTdHJpbmcgbmV3Q2FuZGlkYXRlID0gY2FuZGlkYXRlICsgcmVtYWluaW5nLmNoYXJBdChpKTsKCQkJU3RyaW5nIG5ld1JlbWFpbmluZyA9CgkJCQlyZW1haW5pbmcuc3Vic3RyaW5nKDAsIGkpICsgcmVtYWluaW5nLnN1YnN0cmluZyhpICsgMSwgcmVtYWluaW5nLmxlbmd0aCgpKTsKCgkJCWZpbmRBbmRQcmludFBlcm11dGF0aW9ucyhuZXdDYW5kaWRhdGUsIG5ld1JlbWFpbmluZywgY291bnRlciAtIDEpOwoJCX0KCX0KCglwcml2YXRlIHN0YXRpYyB2b2lkIGZpbmRBbmRQcmludFBlcm11dGF0aW9uc0NoYXJBcnJheUFsdGVybmF0aXZlKGNoYXJbXSBjLCBpbnQgY3VycmVudEluZGV4KSB7CgkJaWYgKGN1cnJlbnRJbmRleCA9PSBjLmxlbmd0aCAtIDEpIHsKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCBjLmxlbmd0aDsgaSsrKSB7CgkJCVN5c3RlbS5vdXQucHJpbnQoY1tpXSk7CgkJCX0KCQkJU3lzdGVtLm91dC5wcmludGxuKCk7CgkJCXJldHVybjsKCQl9CgoJCWZvciAoaW50IGkgPSBjdXJyZW50SW5kZXg7IGkgPCBjLmxlbmd0aDsgaSsrKSB7CgkJCXN3YXAoYywgY3VycmVudEluZGV4LCBpKTsKCQkJZmluZEFuZFByaW50UGVybXV0YXRpb25zQ2hhckFycmF5QWx0ZXJuYXRpdmUoYywgY3VycmVudEluZGV4ICsgMSk7CgkJCXN3YXAoYywgY3VycmVudEluZGV4LCBpKTsKCQl9Cgl9CgoJcHJpdmF0ZSBzdGF0aWMgdm9pZCBzd2FwKGNoYXJbXSBjLCBpbnQgeCwgaW50IHkpIHsKCQljaGFyIHRlbXAgPSBjW3hdOwoJCWNbeF0gPSBjW3ldOwoJCWNbeV0gPSB0ZW1wOwoJfQp9